home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / superopt.lha / superopt-2.2 / superopt.c < prev    next >
C/C++ Source or Header  |  1993-02-15  |  91KB  |  2,989 lines
  1. /* Superoptimizer.  Finds the shortest instruction sequences for an
  2.    arbitrary function f(x,y) where x and y are integers.  The algorithm is
  3.    based on exhaustive search with backtracking and iterative deepening.
  4.  
  5.    Copyright (C) 1991, 1992 Free Software Foundation, Inc.
  6.  
  7.    This program is free software; you can redistribute it and/or modify it
  8.    under the terms of the GNU General Public License as published by the
  9.    Free Software Foundation; either version 2, or (at your option) any
  10.    later version.
  11.  
  12.    This program is distributed in the hope that it will be useful, but
  13.    WITHOUT ANY WARRANTY; without even the implied warranty of
  14.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15.    General Public License for more details.
  16.  
  17.    You should have received a copy of the GNU General Public License along
  18.    with this program; see the file COPYING.  If not, write to the Free
  19.    Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. #include <stdio.h>
  22.  
  23. #include "superopt.h"
  24. #include "run_program.def"
  25. #include "version.h"
  26.  
  27. int goal_function_arity;
  28. enum goal_func goal_function;
  29. word (*eval_goal_function) (const word *);
  30.  
  31. int flag_output_assembler = 0;
  32. int flag_use_carry = 1;
  33.  
  34. /* Counts the number of solutions found.  Flags to top loop that it should
  35.    not go deeper.  */
  36. int success;
  37.  
  38. #ifdef TIMING
  39. #ifndef USG
  40. #include <sys/time.h>
  41. #include <sys/resource.h>
  42.  
  43. unsigned long
  44. cputime ()
  45. {
  46.     struct rusage rus;
  47.  
  48.     getrusage (0, &rus);
  49.     return rus.ru_utime.tv_sec * 1000 + rus.ru_utime.tv_usec / 1000;
  50. }
  51. #else
  52. #include <time.h>
  53.  
  54. unsigned long
  55. cputime ()
  56. {
  57.   return clock () / 1000;
  58. }
  59. #endif
  60. int timings[100];
  61. #endif
  62.  
  63. #ifdef STATISTICS
  64. unsigned int heuristic_reject_count = 0;
  65. unsigned int heuristic_accept_count = 0;
  66. #endif
  67.  
  68. char *insn_name[] =
  69. {
  70. #undef    DEF_INSN
  71. #define DEF_INSN(SYM,CLASS,NAME) NAME,
  72. #include "insn.def"
  73. };
  74.  
  75. char insn_class[] =
  76. {
  77. #undef    DEF_INSN
  78. #define DEF_INSN(SYM,CLASS,NAME) CLASS,
  79. #include "insn.def"
  80. };
  81.  
  82. /* Initialize the "immediate" values in the top registers.  */
  83. void
  84. init_immediates(word *values)
  85. {
  86.   int i;
  87.   for (i = -1; i < BITS_PER_WORD; i++)
  88.     values[0x20 + i] = i;
  89.  
  90.   values[0x20 - 2] = VALUE_MIN_SIGNED;
  91.   values[0x20 - 3] = VALUE_MAX_SIGNED;
  92. }
  93.  
  94. inline word
  95. random_word(void)
  96. {
  97. #ifdef __hpux
  98.   return mrand48();
  99. #else
  100.   /* random returns 31 bits.  We need 32.  */
  101.   return random() ^ (random() << 1);
  102. #endif
  103. }
  104.  
  105. char *
  106. xrealloc (ptr, size)
  107.      char *ptr;
  108.      unsigned size;
  109. {
  110.   char *result = (char *) realloc (ptr, size);
  111.   if (!result)
  112.     abort ();
  113.   return result;
  114. }
  115.  
  116. char *
  117. xmalloc (size)
  118.      unsigned size;
  119. {
  120.   register char *val = (char *) malloc (size);
  121.  
  122.   if (val == 0)
  123.     abort ();
  124.   return val;
  125. }
  126.  
  127. #define RECURSE(opcode, s1, s2, prune_hint) \
  128.   recurse(opcode, n_values, s1, s2, v, 1, sequence, n_insns, values,    \
  129.       n_values + 1, goal_value, allowed_cost, co, prune_hint)
  130. #define CRECURSE_2OP(opcode, d, s1, s2, cost, prune_hint) \
  131.   recurse(opcode, d, s1, s2, v, cost, sequence, n_insns, values,    \
  132.       n_values, goal_value, allowed_cost, co, prune_hint)
  133. #define CRECURSE_NEW(opcode, d, s1, s2, cost, prune_hint) \
  134.   recurse(opcode, d, s1, s2, v, cost, sequence, n_insns, values,    \
  135.       n_values + 1, goal_value, allowed_cost, co, prune_hint)
  136.  
  137. /* Save the last generated instruction and recursively call `synth', if we
  138.    are not at a leaf node.  Otherwise test the computed value and
  139.    back-track.  This function is extremely critical for the performance!
  140.  
  141.    OPCODE is the opcode of the insn that was just generated.
  142.  
  143.    D is the destination register.
  144.  
  145.    S1 is the left source register or immediate reference.  It is an
  146.    immediate reference if IMMEDIATE_P(S1) is true.
  147.  
  148.    S2 is the right source register or immediate reference.  It is an
  149.    immediate reference if IMMEDIATE_P(S2) is true.
  150.  
  151.    V is the computed result from "rD = rS1 OPCODE rS2".
  152.  
  153.    COST is the cost of OPCODE with the the actual operands.
  154.  
  155.    SEQUENCE is the insn sequence so far, excluding the just generated insn.
  156.  
  157.    N_INSNS is the number of insns in SEQUENCE.
  158.  
  159.    VALUES contains the values in register 0..N_VALUES.
  160.  
  161.    N_VALUES is the number of registers that have been assigned values by
  162.    the insns so far.
  163.  
  164.    GOAL_VALUE is the value we aim at, when the sequence is ready.
  165.  
  166.    ALLOWED_COST is the maximum allowed cost of the remaining sequence.
  167.  
  168.    CY is the carry flag.  It is negative if it has an undefined value (this
  169.    for pruning the search tree), and otherwise takes the values 0 or 1
  170.    according to the conventions of the current target.
  171.  
  172.    PRUNE_HINT contains flags to assist pruning of the search tree.  */
  173.  
  174. static inline void
  175. recurse(opcode_t opcode,
  176.     int d,
  177.     int s1,
  178.     int s2,
  179.     word v,
  180.     int cost,
  181.     insn_t *sequence,
  182.     int n_insns,
  183.     word *values,
  184.     int n_values,
  185.     const word goal_value,
  186.     int allowed_cost,
  187.     int cy,
  188.     int prune_flags)
  189. {
  190.   insn_t insn;
  191.  
  192.   /* Update the remaining allowed cost with the cost of the last
  193.      instruction.  */
  194.   allowed_cost -= cost;
  195.  
  196.   if (allowed_cost > 0)
  197.     {
  198.       /* ALLOWED_COST is still positive, meaning we can generate more
  199.      instructions.  */
  200.       word old_d;
  201.  
  202.       old_d = values[d];    /* Remember old value of dest. reg.  */
  203.       values[d] = v;
  204.  
  205. #if __GNUC__
  206.       sequence[n_insns] = (insn_t) {opcode, s1, s2, d};
  207. #else
  208.       insn.opcode = opcode;
  209.       insn.s1 = s1;
  210.       insn.s2 = s2;
  211.       insn.d = d;
  212.       sequence[n_insns] = insn;
  213. #endif
  214.  
  215.       synth(sequence, n_insns + 1, values, n_values,
  216.         goal_value, allowed_cost, cy, prune_flags);
  217.  
  218.       values[d] = old_d;    /* Restore value of dest. reg. */
  219.     }
  220.   else if (goal_value == v)
  221.     {
  222.       /* We are at a leaf node and got the right answer for the
  223.      random value operands.  However, we probably have an
  224.      incorrect sequence.  Call test_sequence to find out.  */
  225.  
  226. #if __GNUC__
  227.       sequence[n_insns] = (insn_t) {opcode, s1, s2, d};
  228. #else
  229.       insn.opcode = opcode;
  230.       insn.s1 = s1;
  231.       insn.s2 = s2;
  232.       insn.d = d;
  233.       sequence[n_insns] = insn;
  234. #endif
  235.       test_sequence(sequence, n_insns + 1);
  236.  
  237. #ifdef STATISTICS
  238.   heuristic_accept_count++;
  239. #endif
  240.  
  241.     }
  242. #ifdef STATISTICS
  243.   else
  244.     heuristic_reject_count++;
  245. #endif
  246. }
  247.  
  248. #define NAME(op) operand_names[op]
  249. static char *operand_names[256]=
  250. {
  251. #if SPARC
  252.   "%i0", "%i1", "%i2", "%i3", "%i4", "%i5", "%i6", "%i7",
  253. #elif RS6000
  254.   "r3", "r4", "r5", "r6", "r7", "r8", "r9", "r10",
  255. #elif M88000
  256.   "r2", "r3", "r4", "r5", "r6", "r7", "r8", "r9",
  257. #elif AM29K
  258.   "lr2", "lr3", "lr4", "lr5", "lr6", "lr7", "lr8", "lr9",
  259. #elif M68000
  260.   "d0", "d1", "d2", "d3", "d4", "d5", "d6", "d7",
  261. #elif I386
  262.   "%eax", "%edx", "%ecx", "%ebx", "%esi", "%edi", "%noooo!", "%crash!!!",
  263. #elif PYR
  264.   "pr0", "pr1", "pr2", "pr3", "pr4", "pr5", "pr6", "pr7",
  265. #elif ALPHA
  266.   "r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7",
  267. #else
  268. #error no register names for this CPU
  269. #endif
  270.   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  271. #if SPARC
  272.   "???%hi(0x7fffffff)","%hi(0x80000000)","-1","%g0","1","2","3","4","5","6",
  273.   "7","8","9","10","11","12","13","14","15","16","17","18","19",
  274.   "20","21","22","23","24","25","26","27","28","29","30","31",
  275. #elif RS6000
  276.   "0x7fff","0x8000","-1","0","1","2","3","4","5","6",
  277.   "7","8","9","10","11","12","13","14","15","16","17","18","19",
  278.   "20","21","22","23","24","25","26","27","28","29","30","31",
  279. #elif M88000
  280.   "hi16(0x7fffffff)","hi16(0x80000000)","-1","r0","1","2","3","4","5","6",
  281.   "7","8","9","10","11","12","13","14","15","16","17","18","19",
  282.   "20","21","22","23","24","25","26","27","28","29","30","31",
  283. #elif AM29K
  284.   "0x7fff","0x8000","-1","0","1","2","3","4","5","6",
  285.   "7","8","9","10","11","12","13","14","15","16","17","18","19",
  286.   "20","21","22","23","24","25","26","27","28","29","30","31",
  287. #elif M68000
  288.   "#0x7fffffff","#0x80000000","#-1","#0","#1","#2","#3","#4","#5","#6",
  289.   "#7","#8","#9","#10","#11","#12","#13","#14","#15","#16","#17","#18","#19",
  290.   "#20","#21","#22","#23","#24","#25","#26","#27","#28","#29","#30","#31",
  291. #elif I386
  292.   "$0x7fffffff","$0x80000000","$-1","$0","$1","$2","$3","$4","$5","$6",
  293.   "$7","$8","$9","$10","$11","$12","$13","$14","$15","$16","$17","$18","$19",
  294.   "$20","$21","$22","$23","$24","$25","$26","$27","$28","$29","$30","$31",
  295. #elif PYR
  296.   "$0x7fffffff","$0x80000000","$-1","$0","$1","$2","$3","$4","$5","$6",
  297.   "$7","$8","$9","$10","$11","$12","$13","$14","$15","$16","$17","$18","$19",
  298.   "$20","$21","$22","$23","$24","$25","$26","$27","$28","$29","$30","$31",
  299. #elif ALPHA
  300.   "0x7fff","0x8000","-1","$31","1","2","3","4","5","6",
  301.   "7","8","9","10","11","12","13","14","15","16","17","18","19",
  302.   "20","21","22","23","24","25","26","27","28","29","30","31",
  303.   "32","33","34","35","36","37","38","39","40","41","42","43",
  304.   "44","45","46","47","48","49","50","51","52","53","54","55",
  305.   "56","57","58","59","60","61","62","63",
  306. #else
  307. #error no constant syntax for this CPU
  308. #endif
  309. };
  310.  
  311. /* Output INSN in assembler mnemonic format on stdout.  */
  312.  
  313. void
  314. output_assembler(insn_t insn)
  315. {
  316.   int d, s1, s2;
  317.  
  318.   d = insn.d;
  319.   s1 = insn.s1;
  320.   s2 = insn.s2;
  321.  
  322.   printf("\t");
  323.   switch (insn.opcode)
  324.     {
  325. #if SPARC
  326.     case COPY:
  327.       if (IMMEDIATE_P(s1) && (IMMEDIATE_VAL(s1) & 0x1fff) == 0)
  328.     printf("sethi    %s,%s",NAME(s1),NAME(d));
  329.       else
  330.     printf("mov    %s,%s",NAME(s1),NAME(d));
  331.       break;
  332.     case ADD:    printf("add    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  333.     case ADD_CI:printf("addx    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  334.     case ADD_CO:printf("addcc    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  335.     case ADD_CIO:printf("addxcc    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  336.     case SUB:
  337.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  338.     printf("xnor    %%g0,%s,%s",NAME(s2),NAME(d));
  339.       else
  340.     printf("sub    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));
  341.       break;
  342.     case SUB_CI:printf("subx    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  343.     case SUB_CO:printf("subcc    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  344.     case SUB_CIO:printf("subxcc    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  345.     case AND:    printf("and    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  346.     case IOR:    printf("or    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  347.     case XOR:    printf("xor    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  348.     case ANDC:    printf("andn    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  349.     case IORC:    printf("orn    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  350.     case EQV:    printf("xnor    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  351.     case LSHIFTR:printf("srl    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  352.     case ASHIFTR:printf("sra    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  353.     case SHIFTL:printf("sll    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  354. #elif RS6000
  355.     case COPY:
  356.       if (IMMEDIATE_P(s1))
  357.     {
  358.       if (IMMEDIATE_VAL(s1) >= 0 && IMMEDIATE_VAL(s1) < 0x8000)
  359.         printf("lil    %s,0x%x",NAME(d),IMMEDIATE_VAL(s1));
  360.       else
  361.         printf("liu    %s,%s",NAME(d),NAME(s1));
  362.     }
  363.       else
  364.     printf("oril    %s,%s,0",NAME(d),NAME(s1));
  365.       break;
  366.     case ADD:
  367.       if (IMMEDIATE_P(s2))
  368.     {
  369.       if (IMMEDIATE_VAL(s2) + 0x4000 < 0x8000)
  370.         printf("cal    %s,%d(%s)",NAME(d),IMMEDIATE_VAL(s2),NAME(s1));
  371.       else if ((IMMEDIATE_VAL(s2) & 0xffff) == 0)
  372.         printf("cau    %s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2) >> 16);
  373.       else
  374.         abort ();
  375.     }
  376.       else
  377.     printf("cax     %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  378.       break;
  379.     case ADD_CO:
  380.       if (IMMEDIATE_P(s2))
  381.     printf("ai    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  382.       else
  383.     printf("a    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  384.       break;
  385.     case ADD_CIO:
  386.       if (IMMEDIATE_P(s2))
  387.     {
  388.       if (IMMEDIATE_VAL(s2) == -1)
  389.         printf("ame    %s,%s",NAME(d),NAME(s1));
  390.       else if (IMMEDIATE_VAL(s2) == 0)
  391.         printf("aze    %s,%s",NAME(d),NAME(s1));
  392.     }
  393.       else
  394.     printf("ae    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  395.       break;
  396.     case SUB:
  397.       if (IMMEDIATE_P(s1))
  398.     {
  399.       if (IMMEDIATE_VAL(s1) == 0)
  400.         printf("neg    %s,%s",NAME(d),NAME(s2));
  401.       else if (IMMEDIATE_VAL(s1) == -1)
  402.         printf("nand    %s,%s,%s",NAME(d),NAME(s2),NAME(s2));
  403.     }
  404.       else abort();
  405.       break;
  406.     case ADC_CO:
  407.       if (IMMEDIATE_P(s1))
  408.     printf("sfi    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  409.       else
  410.     printf("sf    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  411.       break;
  412.     case ADC_CIO:
  413.       if (IMMEDIATE_P(s1))
  414.     {
  415.       if (IMMEDIATE_VAL(s1) == -1)
  416.         printf("sfme    %s,%s",NAME(d),NAME(s2));
  417.       else if (IMMEDIATE_VAL(s1) == 0)
  418.         printf("sfze    %s,%s",NAME(d),NAME(s2));
  419.       else abort();
  420.     }
  421.       else
  422.     printf("sfe    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  423.       break;
  424.     case AND:
  425.       if (IMMEDIATE_P(s2))
  426.     {
  427.       if (IMMEDIATE_VAL(s2) == 0x80000000)
  428.         printf("rlinm    %s,%s,0,0,0",NAME(d),NAME(s1));
  429.       else if (IMMEDIATE_VAL(s2) == 0x7fffffff)
  430.         printf("rlinm    %s,%s,0,1,31",NAME(d),NAME(s1));
  431.       else if (IMMEDIATE_VAL(s2) == 1)
  432.         printf("rlinm    %s,%s,0,31,31",NAME(d),NAME(s1));
  433.       else abort();
  434.     }
  435.       else
  436.     printf("and    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  437.       break;
  438.     case IOR:
  439.       if (IMMEDIATE_P(s2))
  440.     {
  441.       if (IMMEDIATE_VAL(s2) == 0x80000000)
  442.         printf("oriu    %s,%s,0x8000",NAME(d),NAME(s1));
  443.       else abort();
  444.     }
  445.       else
  446.     printf("or    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  447.       break;
  448.     case XOR:
  449.       if (IMMEDIATE_P(s2))
  450.     {
  451.       if (IMMEDIATE_VAL(s2) == 1)
  452.         printf("xoril\t%s,%s,1",NAME(d),NAME(s1));
  453.       else if (IMMEDIATE_VAL(s2) == 0x80000000)
  454.         printf("xoriu\t%s,%s,0x8000",NAME(d),NAME(s1));
  455.       else abort();
  456.     }
  457.       else
  458.     printf("xor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  459.       break;
  460.     case ANDC:    printf("andc    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  461.     case IORC:    printf("orc    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  462.     case EQV:    printf("eqv    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  463.     case NAND:    printf("nand    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  464.     case NOR:    printf("nor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  465.     case LSHIFTR:
  466.       if (IMMEDIATE_P(s2))
  467.     printf("sri    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  468.       else
  469.     printf("sre    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  470.       break;
  471.     case ASHIFTR_CON:
  472.       if (IMMEDIATE_P(s2))
  473.     printf("srai    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  474.       else
  475.     printf("srea    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  476.       break;
  477.     case SHIFTL:
  478.       if (IMMEDIATE_P(s2))
  479.     printf("sli    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  480.       else
  481.     printf("sle    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  482.       break;
  483.     case ROTATEL:
  484.       if (IMMEDIATE_P(s2))
  485.     printf("rlinm    %s,%s,%s,0,31",NAME(d),NAME(s1),NAME(s2));
  486.       else
  487.     printf("rlnm    %s,%s,%s,0,31",NAME(d),NAME(s1),NAME(s2));
  488.       break;
  489.     case ABSVAL:printf("abs    %s,%s",NAME(d),NAME(s1));break;
  490.     case NABSVAL:printf("nabs    %s,%s",NAME(d),NAME(s1));break;
  491.     case DOZ:
  492.       if (IMMEDIATE_P(s1))
  493.     printf("dozi    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  494.       else
  495.     printf("doz    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  496.       break;
  497.     case MUL:
  498.       if (IMMEDIATE_P(s1))
  499.     printf("muli    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  500.       else
  501.     printf("muls    %s,%s,%s",NAME(d),NAME(s2),NAME(s1));
  502.       break;
  503.     case CLZ:
  504.       printf("cntlz    %s,%s",NAME(d),NAME(s1));break;
  505.       
  506. #elif M88000
  507.     case COPY:
  508.       if (IMMEDIATE_P(s1))
  509.     {
  510.       if ((IMMEDIATE_VAL(s1) & 0xffff) == 0)
  511.         printf("or.u    %s,r0,0x%x",NAME(d),IMMEDIATE_VAL(s1));
  512.       else if ((IMMEDIATE_VAL(s1) & 0xffff0000) == 0)
  513.         printf("or    %s,r0,0x%x",NAME(d),IMMEDIATE_VAL(s1));
  514.       else if ((IMMEDIATE_VAL(s1) & 0xffff0000) == 0xffff0000)
  515.         printf("subu    %s,r0,0x%x",NAME(d),-IMMEDIATE_VAL(s1));
  516.       else
  517.         {
  518.           word x = IMMEDIATE_VAL(s1);
  519.           int i, j;
  520.           for (i = 31; i > 0; i--)
  521.         if ((x & (1 << i)) != 0)
  522.           break;
  523.           for (j = i; j >= 0; j--)
  524.         if ((x & (1 << j)) == 0)
  525.           break;
  526.           printf("set    %s,r0,%d<%d>",NAME(d), i - j, j + 1);
  527.         }
  528.     }
  529.       else
  530.     printf("or    %s,%s",NAME(d),NAME(s1));
  531.       break;
  532.     case ADD:    printf("addu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  533.     case ADD_CI:printf("addu.ci    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  534.     case ADD_CO:printf("addu.co    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  535.     case ADD_CIO:
  536.       if (IMMEDIATE_P(s2))
  537.     {
  538.       if (IMMEDIATE_VAL(s2) == -1)
  539.         {
  540.           printf("subu.cio %s,%s,r0",NAME(d),NAME(s1));
  541.           break;
  542.         }
  543.       if (IMMEDIATE_VAL(s2) != 0)
  544.         abort();
  545.     }
  546.       printf("addu.cio %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  547.       break;      
  548.     case SUB:
  549.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  550.     printf("xor.c    %s,%s,r0",NAME(d),NAME(s2));
  551.       else
  552.     printf("subu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  553.       break;
  554.     case ADC_CI:printf("subu.ci    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  555.     case ADC_CO:printf("subu.co    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  556.     case ADC_CIO:printf("subu.cio %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  557.     case AND:
  558.       if (IMMEDIATE_P(s2))
  559.     {
  560.       if (IMMEDIATE_VAL(s2) == 0x80000000)
  561.         printf("mask.u    %s,%s,0x8000",NAME(d),NAME(s1));
  562.       else if (IMMEDIATE_VAL(s2) == 0x7fffffff)
  563.         printf("and.u    %s,%s,0x7fff",NAME(d),NAME(s1));
  564.       else if (IMMEDIATE_VAL(s2) == 1)
  565.         printf("mask    %s,%s,1",NAME(d),NAME(s1));
  566.       else abort();
  567.     }
  568.       else
  569.     printf("and    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  570.       break;
  571.     case IOR:
  572.       if (IMMEDIATE_P(s2))
  573.     {
  574.       if ((IMMEDIATE_VAL(s2) & 0xffff) == 0)
  575.         printf("or.u    %s,%s,0x%x",NAME(d),NAME(s1),
  576.            IMMEDIATE_VAL(s2)>>16);
  577.       else if (IMMEDIATE_VAL(s2) < 0x10000)
  578.         printf("or    %s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  579.       else abort();
  580.     }
  581.       else
  582.     printf("or    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  583.       break;
  584.     case XOR:
  585.       if (IMMEDIATE_P(s2))
  586.     {
  587.       if ((IMMEDIATE_VAL(s2) & 0xffff) == 0)
  588.         printf("xor.u    %s,%s,0x%x",NAME(d),NAME(s1),
  589.            IMMEDIATE_VAL(s2)>>16);
  590.       else if (IMMEDIATE_VAL(s2) < 0x10000)
  591.         printf("xor    %s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  592.       else abort();
  593.     }
  594.       else
  595.     printf("xor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  596.       break;
  597.     case ANDC:    printf("and.c    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  598.     case IORC:    printf("or.c    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  599.     case EQV:    printf("xor.c    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  600.     case LSHIFTR:printf("extu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  601.     case ASHIFTR:printf("ext    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  602.     case SHIFTL:printf("mak    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  603.     case ROTATEL:
  604.       printf("rot    %s,%s,%d",NAME(d),NAME(s1),32-IMMEDIATE_VAL(s2));
  605.       break;
  606.     case FF1:
  607.       printf("ff1    %s,%s",NAME(d),NAME(s1)); break;
  608.     case FF0:
  609.       printf("ff0    %s,%s",NAME(d),NAME(s1)); break;
  610.     case CMPPAR:
  611.       if (IMMEDIATE_P(s2))
  612.     printf("cmp    %s,%s,0x%x",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  613.       else if (IMMEDIATE_P(s1))
  614.     printf("cmp    %s,r0,%s",NAME(d),NAME(s2));
  615.       else
  616.     printf("cmp    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  617.       break;
  618.     case EXTS1:
  619.       printf("ext    %s,%s,1<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  620.       break;      
  621.     case EXTS2:
  622.       printf("ext    %s,%s,2<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  623.       break;      
  624.     case EXTU1:
  625.       printf("extu    %s,%s,1<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  626.       break;      
  627.     case EXTU2:
  628.       printf("extu    %s,%s,2<%d>",NAME(d),NAME(s1),IMMEDIATE_VAL(s2));
  629.       break;      
  630.     case MUL:
  631.       printf("mul    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  632.       break;      
  633. #elif AM29K
  634.     case COPY:
  635.       if (IMMEDIATE_P(s1))
  636.     {
  637.       if (IMMEDIATE_VAL(s1) < 0x10000)
  638.         printf("const    %s,0x%x",NAME(d),IMMEDIATE_VAL(s1));
  639.       else if (-IMMEDIATE_VAL(s1) < 0x10000)
  640.         printf("constn    %s,-0x%x",NAME(d),-IMMEDIATE_VAL(s1));
  641.       else if (IMMEDIATE_VAL(s1) == 0x80000000)
  642.         printf("cpeq    %s,gr1,gr1",NAME(d));
  643.       else abort();
  644.     }
  645.       else
  646.     printf("or    %s,%s,0",NAME(d),NAME(s1));
  647.       break;
  648.     case ADD_CO:
  649.       if (IMMEDIATE_P(s2) && (signed_word) IMMEDIATE_VAL(s2) < 0)
  650.     printf("sub    %s,%s,0x%x",NAME(d),NAME(s1),-IMMEDIATE_VAL(s2));
  651.       else
  652.     printf("add    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  653.       break;
  654.     case ADD_CIO:
  655.       if (IMMEDIATE_P(s2) && (signed_word) IMMEDIATE_VAL(s2) < 0)
  656.     printf("subc    %s,%s,0x%x",NAME(d),NAME(s1),-IMMEDIATE_VAL(s2));
  657.       else
  658.     printf("addc    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  659.       break;
  660.     case SUB:
  661.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  662.     printf("nor    %s,%s,0",NAME(d),NAME(s2));
  663.       else abort();
  664.       break;
  665.     case ADC_CO:printf("sub    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  666.     case ADC_CIO:printf("subc    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  667.     case AND:    printf("and    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  668.     case IOR:    printf("or    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  669.     case XOR:    printf("xor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  670.     case ANDC:    printf("andn    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  671.     case EQV:    printf("xnor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  672.     case NAND:    printf("nand    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  673.     case NOR:    printf("nor    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  674.     case LSHIFTR:printf("srl    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  675.     case ASHIFTR:printf("sra    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  676.     case SHIFTL:printf("sll    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  677.     case CPEQ:    printf("cpeq    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  678.     case CPGE:    printf("cpge    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  679.     case CPGEU:    printf("cpgeu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  680.     case CPGT:    printf("cpgt    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  681.     case CPGTU:    printf("cpgtu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  682.     case CPLE:    printf("cple    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  683.     case CPLEU:    printf("cpleu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  684.     case CPLT:    printf("cplt    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  685.     case CPLTU:    printf("cpltu    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  686.     case CPNEQ:    printf("cpneq    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));break;
  687.     case MUL:
  688.       printf("multiply    %s,%s,%s",NAME(d),NAME(s1),NAME(s2));
  689.       break;      
  690.     case CLZ:
  691.       printf("clz    %s,%s",NAME(d),NAME(s1));break;
  692. #elif M68000
  693.     case COPY:
  694.       if (IMMEDIATE_P(s1))
  695.     {
  696.       if ((signed_word) IMMEDIATE_VAL(s1) >= -128
  697.           && (signed_word) IMMEDIATE_VAL(s1) < 128)
  698.         {
  699.           printf("moveq    #%ld,%s", IMMEDIATE_VAL(s1),NAME(d));
  700.           break;
  701.         }
  702.     }
  703.       printf("movel    %s,%s",NAME(s1),NAME(d));
  704.       break;
  705.     case EXCHANGE:
  706.       printf("exgl    %s,%s",NAME(s2),NAME(d));break;
  707.     case ADD_CO:
  708.       if (IMMEDIATE_P(s2)
  709.       && IMMEDIATE_VAL(s2) >= 1 && IMMEDIATE_VAL(s2) <= 8)
  710.     printf("addql    %s,%s",NAME(s2),NAME(d));
  711.       else
  712.     printf("addl    %s,%s",NAME(s2),NAME(d));
  713.       break;
  714.     case ADD_CIO:
  715.       printf("addxl    %s,%s",NAME(s2),NAME(d));break;
  716.     case SUB:
  717.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  718.     printf("notl    %s",NAME(d));
  719.       else abort();
  720.       break;
  721.     case SUB_CO:
  722.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == 0)
  723.     printf("negl    %s",NAME(d));
  724.       else if (IMMEDIATE_P(s2)
  725.            && IMMEDIATE_VAL(s2) >= 1 && IMMEDIATE_VAL(s2) <= 8)
  726.     printf("subql    %s,%s",NAME(s2),NAME(d));
  727.       else
  728.     printf("subl    %s,%s",NAME(s2),NAME(d));
  729.       break;
  730.     case SUB_CIO:
  731.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == 0)
  732.     printf("negxl    %s",NAME(d));
  733.       else
  734.     printf("subxl    %s,%s",NAME(s2),NAME(d));
  735.       break;
  736.     case AND:
  737.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x8000 < 0x10000)
  738.     printf("andw    %s,%s",NAME(s2),NAME(d));
  739.       else
  740.     printf("andl    %s,%s",NAME(s2),NAME(d));
  741.       break;
  742.     case IOR:
  743.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x8000 < 0x10000)
  744.     printf("orw    %s,%s",NAME(s2),NAME(d));
  745.       else
  746.     printf("orl    %s,%s",NAME(s2),NAME(d));
  747.       break;
  748.     case XOR:
  749.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x8000 < 0x10000)
  750.     printf("eorw    %s,%s",NAME(s2),NAME(d));
  751.       else
  752.     printf("eorl    %s,%s",NAME(s2),NAME(d));
  753.       break;
  754.     case LSHIFTR_CO:
  755.       printf("lsrl    %s,%s",NAME(s2),NAME(d));break;
  756.     case ASHIFTR_CO:
  757.       printf("asrl    %s,%s",NAME(s2),NAME(d));break;
  758.     case SHIFTL_CO:
  759.       printf("lsll    %s,%s",NAME(s2),NAME(d));break;
  760.     case ROTATEL_CO:
  761.       printf("roll    %s,%s",NAME(s2),NAME(d));break;
  762.     case ROTATEXL_CIO:
  763.       printf("roxll    %s,%s",NAME(s2),NAME(d));break;
  764.     case MUL:
  765.       printf("mulsl    %s,%s",NAME(s2),NAME(d));break;      
  766. #elif I386
  767.     case COPY:
  768.       printf("movl    %s,%s",NAME(s1),NAME(d));break;
  769.     case EXCHANGE:
  770.       printf("xchgl    %s,%s",NAME(s2),NAME(d));break;
  771.     case ADD:
  772.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) == 1)
  773.     printf("incl    %s",NAME(d));
  774.       else abort();
  775.       break;
  776.     case ADD_CO:
  777.       printf("addl    %s,%s",NAME(s2),NAME(d));break;
  778.     case ADD_CIO:
  779.       printf("adcl    %s,%s",NAME(s2),NAME(d));break;
  780.     case SUB:
  781.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) == 1)
  782.     printf("decl    %s",NAME(d));
  783.       else if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  784.     printf("notl    %s",NAME(d));
  785.       else abort();
  786.       break;
  787.     case SUB_CO:
  788.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == 0)
  789.     printf("negl    %s",NAME(d));
  790.       else
  791.     printf("subl    %s,%s",NAME(s2),NAME(d));
  792.       break;
  793.     case SUB_CIO:
  794.       printf("sbbl    %s,%s",NAME(s2),NAME(d));break;
  795.     case CMP:
  796.       printf("cmpl    %s,%s",NAME(s2),NAME(s1));break;
  797.     case AND_RC:
  798.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x80 < 0x100)
  799.     printf("andb    $%d,%s",IMMEDIATE_VAL(s2),NAME(d));
  800.       else
  801.     printf("andl    %s,%s",NAME(s2),NAME(d));
  802.       break;
  803.     case IOR_RC:
  804.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x80 < 0x100)
  805.     printf("orb    $%d,%s",IMMEDIATE_VAL(s2),NAME(d));
  806.       else
  807.     printf("orl    %s,%s",NAME(s2),NAME(d));
  808.       break;
  809.     case XOR_RC:
  810.       if (IMMEDIATE_P(s2) && IMMEDIATE_VAL(s2) + 0x80 < 0x100)
  811.     printf("xorb    $%d,%s",IMMEDIATE_VAL(s2),NAME(d));
  812.       else
  813.     printf("xorl    %s,%s",NAME(s2),NAME(d));
  814.       break;
  815.     case LSHIFTR_CO:
  816.       printf("shrl    %s,%s",NAME(s2),NAME(d));break;
  817.     case ASHIFTR_CO:
  818.       printf("sarl    %s,%s",NAME(s2),NAME(d));break;
  819.     case SHIFTL_CO:
  820.       printf("shll    %s,%s",NAME(s2),NAME(d));break;
  821.     case ROTATEL_CO:
  822.       printf("roll    %s,%s",NAME(s2),NAME(d));break;
  823.     case ROTATEXL_CIO:
  824.       printf("rlcl    %s,%s",NAME(s2),NAME(d));break;
  825.     case COMCY:
  826.       printf("cmc");break;
  827.     case MUL:
  828.       printf("imull    %s,%s",NAME(s2),NAME(d));break;      
  829. #elif PYR
  830.     case COPY:
  831.       printf("movw    %s,%s",NAME(s1),NAME(d));break;
  832.     case EXCHANGE:
  833.       printf("xchw    %s,%s",NAME(s2),NAME(d));break;
  834.     case ADD:
  835.       printf("mova    0x%x(%s),%s",IMMEDIATE_VAL(s2),NAME(s1),NAME(d));
  836.       break;
  837.     case ADD_CO:
  838.       printf("addw    %s,%s",NAME(s2),NAME(d));break;
  839.     case ADD_CIO:
  840.       printf("addwc    %s,%s",NAME(s2),NAME(d));break;
  841.     case ADC_CO:
  842.       printf("subw    %s,%s",NAME(s2),NAME(d));break;
  843.     case ADC_CIO:
  844.       printf("subwb    %s,%s",NAME(s2),NAME(d));break;
  845.     case AND_CC:
  846.       printf("andw    %s,%s",NAME(s2),NAME(d));break;
  847.     case IOR_CC:
  848.       printf("orw    %s,%s",NAME(s2),NAME(d));break;
  849.     case XOR_CC:
  850.       printf("xorw    %s,%s",NAME(s2),NAME(d)); break;
  851.     case ANDC_CC:
  852.       printf("bicw    %s,%s",NAME(s2),NAME(d)); break;
  853.     case LSHIFTR_CO:
  854.       printf("lshrw    %s,%s",NAME(s2),NAME(d));break;
  855.     case ASHIFTR_CO:
  856.       printf("ashrw    %s,%s",NAME(s2),NAME(d));break;
  857.     case SHIFTL_CO:
  858.       printf("lshlw    %s,%s",NAME(s2),NAME(d));break;
  859.     case MUL:
  860.       printf("mulw    %s,%s",NAME(s2),NAME(d));break;      
  861. #elif ALPHA
  862.     case ADD:    printf("addq    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  863.     case SUB:
  864.       if (IMMEDIATE_P(s1) && IMMEDIATE_VAL(s1) == -1)
  865.     printf("ornot    $31,%s,%s",NAME(s2),NAME(d));
  866.       else
  867.     printf("subq    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));
  868.       break;
  869.     case AND:    printf("and    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  870.     case IOR:    printf("bis    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  871.     case XOR:    printf("xor    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  872.     case ANDC:    printf("bic    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  873.     case IORC:    printf("ornot    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  874.     case EQV:    printf("eqv    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  875.     case LSHIFTR:printf("srl    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  876.     case ASHIFTR:printf("sra    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  877.     case SHIFTL:printf("sll    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  878.     case CMPEQ:    printf("cmpeq    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  879.     case CMPLE:    printf("cmple    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  880.     case CMPLEU:printf("cmpleu    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  881.     case CMPLT:    printf("cmplt    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  882.     case CMPLTU:printf("cmpltu    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  883.     case CMOVEQ:printf("cmoveq    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  884.     case CMOVNE:printf("cmovne    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  885.     case CMOVLT:printf("cmovlt    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  886.     case CMOVGE:printf("cmovge    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  887.     case CMOVLE:printf("cmovle    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  888.     case CMOVGT:printf("cmovgt    %s,%s,%s",NAME(s1),NAME(s2),NAME(d));break;
  889. #else
  890. #error no assembler output code for this CPU
  891. #endif
  892.     default:abort();
  893.     }
  894.   printf("\n");
  895. }
  896.  
  897. word tvalues[0x100];
  898.  
  899. /* TEST_SETS contains sets of input values and corresponding goal value used
  900.    to test the correctness of a sequence.  N_TEST_SETS says how many sets
  901.    are defined.  */
  902. word *test_sets;
  903. int n_test_sets;
  904.  
  905. word test_operands[] =
  906. {
  907.   0,
  908.   1,
  909.   -1,
  910.   -2,
  911.   VALUE_MIN_SIGNED,
  912.   VALUE_MAX_SIGNED,
  913.   VALUE_MIN_SIGNED + 1,
  914.   VALUE_MAX_SIGNED - 1,
  915. };
  916. #define N_TEST_OPERANDS (sizeof(test_operands)/sizeof(test_operands[0]))
  917.  
  918. void
  919. init_test_sets()
  920. {
  921.   unsigned int loop_vars[8];
  922.   int pc, i, j;
  923.   word *test_set;
  924.   const int arity = goal_function_arity;
  925.   word (*eval) (const word *) = eval_goal_function;
  926.  
  927.   if (sizeof (loop_vars) / sizeof (loop_vars[0]) <= arity)
  928.     abort ();
  929.  
  930.   /* Allocate enough space in TEST_SETS for all combinations of TEST_OPERANDS
  931.      and an additional 10,000 random test sets.  */
  932.   {
  933.     static int n_words;
  934.  
  935.     j = 1 + arity;
  936.     for (i = arity - 1; i >= 0; i--)
  937.       j *= N_TEST_OPERANDS;
  938.  
  939.     j += (1 + arity) * 10000;
  940.  
  941.     if (n_words < j)
  942.       {
  943.     test_sets = (n_words == 0
  944.              ? (word *) xmalloc (sizeof (word) * j)
  945.              : (word *) xrealloc (test_sets, sizeof (word) * j));
  946.     n_words = j;
  947.       }
  948.   }
  949.  
  950.   test_set = test_sets;
  951.   j = 0;
  952.  
  953.   /* Start with all combinations of operands from TEST_OPERANDS.  */
  954.   for (i = arity - 1; i >= 0; i--)
  955.     loop_vars[i] = 0;
  956.   for (;;)
  957.     {
  958.       for (i = arity - 1; i >= 0; i--)
  959.     tvalues[i] = *test_set++ = test_operands[loop_vars[i]];
  960.  
  961.       /* Get the desired value for the current operand values.  */
  962.       *test_set++ = (*eval)(tvalues);
  963.       j++;
  964.  
  965.       /* General loop control.  This implements ARITY loops using induction
  966.      variables in loop_vars[0] through loop_vars[ARITY - 1].  */
  967.       i = 0;
  968.       loop_vars[i] = (loop_vars[i] + 1) % N_TEST_OPERANDS;
  969.       while (loop_vars[i] == 0)
  970.     {
  971.       i++;
  972.       if (i >= arity)
  973.         goto random;
  974.       loop_vars[i] = (loop_vars[i] + 1) % N_TEST_OPERANDS;
  975.     }
  976.     }
  977.  
  978.   /* Now add the additional random test sets.  */
  979.  random:  
  980.   for (i = 9999; i >= 0; i--)
  981.     {
  982.       for (pc = arity - 1; pc >= 0; pc--)
  983.     tvalues[pc] = *test_set++ = random_word();
  984.  
  985.       *test_set++ = (*eval)(tvalues);
  986.       j++;
  987.     }
  988.  
  989.   n_test_sets = j;
  990. }
  991.  
  992. /* Test the correctness of a sequence in SEQUENCE[0] through
  993.    SEQUENCE[N_INSNS - 1].  */
  994.  
  995. void
  996. test_sequence(insn_t *sequence, int n_insns)
  997. {
  998.   int pc;
  999.   int i, j;
  1000.   word *test_set = test_sets;
  1001.   const int arity = goal_function_arity;
  1002.  
  1003.   /* Test each of the precomputed values.  */
  1004.   for (j = n_test_sets; j > 0; j--)
  1005.     {
  1006.       /* Update the tvalues array in each iteration, as execution of the
  1007.      sequence might clobber the values.  (On 2-operand machines.)  */
  1008.       for (i = arity - 1; i >= 0; i--)
  1009.     tvalues[i] = *test_set++;
  1010.  
  1011.       /* Execute the synthesised sequence for the current operand
  1012.      values.  */
  1013.       run_program (sequence, n_insns, tvalues);
  1014.       if (tvalues[sequence[n_insns - 1].d] != *test_set++)
  1015.     {
  1016.       /* Adaptively rearrange the order of the tests.  This set of test
  1017.          values is better than all that preceed it.  The optimal
  1018.          ordering changes with the search space.  */
  1019.       if ((j = n_test_sets - j) != 0)
  1020.         {
  1021.           int k = j >> 1;
  1022.           j *= (arity + 1);
  1023.           k *= (arity + 1);
  1024.           for (i = 0; i <= arity; i++)
  1025.         {
  1026.           word t = test_sets[j + i];
  1027.           test_sets[j + i] = test_sets[k + i];
  1028.           test_sets[k + i] = t;
  1029.         }
  1030.         }
  1031.       return;
  1032.     }
  1033.     }
  1034.  
  1035.   /* The tests passed.  Print the instruction sequence.  */
  1036.   if (success == 0)
  1037.     printf("\n");
  1038.   success++;
  1039.  
  1040.   printf("%d:", success);
  1041.   for (pc = 0; pc < n_insns; pc++)
  1042.     {
  1043.       insn_t insn;
  1044.  
  1045.       insn = sequence[pc];
  1046.       if (flag_output_assembler)
  1047.     output_assembler(insn);
  1048.       else
  1049.     {
  1050.       if (insn.opcode == CMP)
  1051.         printf("\t%s(", GET_INSN_NAME(insn.opcode));
  1052.       else
  1053.         printf("\tr%u:=%s(", insn.d, GET_INSN_NAME(insn.opcode));
  1054.       if (IMMEDIATE_P(insn.s1))
  1055.         {
  1056.           if ((signed_word) IMMEDIATE_VAL(insn.s1) >= 10
  1057.           || (signed_word) IMMEDIATE_VAL(insn.s1) <= -10)
  1058.         printf("0x%lx", IMMEDIATE_VAL(insn.s1));
  1059.           else
  1060.         printf("%ld", IMMEDIATE_VAL(insn.s1));
  1061.         }
  1062.       else
  1063.         printf("r%u", insn.s1);
  1064.  
  1065.       if (!UNARY_OPERATION(insn))
  1066.         {
  1067.           if (IMMEDIATE_P(insn.s2))
  1068.         {
  1069.           if ((signed_word) IMMEDIATE_VAL(insn.s2) >= 10
  1070.               || (signed_word) IMMEDIATE_VAL(insn.s2) <= -10)
  1071.             printf(",0x%lx", IMMEDIATE_VAL(insn.s2));
  1072.           else
  1073.             printf(",%ld", IMMEDIATE_VAL(insn.s2));
  1074.         }
  1075.           else
  1076.         printf(",r%u", insn.s2);
  1077.         }
  1078.       printf(")\n");
  1079.     }
  1080.     }
  1081.   fflush(stdout);
  1082. }
  1083.  
  1084.  
  1085. /* Recursively investigate all possible instruction sequences for the
  1086.    current target.
  1087.  
  1088.    SEQUENCE contains the instructions defined so far.
  1089.  
  1090.    N_INSNS is the number of instructions, including the one we will
  1091.    generate this time, in SEQUENCE.
  1092.  
  1093.    VALUES contains the values in register 0..N_VALUES.
  1094.  
  1095.    N_VALUES is the number of registers that have been assigned values by
  1096.    the insns so far.
  1097.  
  1098.    GOAL_VALUE is the value we aim at, when the sequence is ready.
  1099.  
  1100.    ALLOWED_COST is the maximum allowed cost of the remaining sequence.
  1101.  
  1102.    CY_IN is the carry flag.  It is negative if no instruction has yet
  1103.    defined it (this to pruning the search tree), and otherwise takes the
  1104.    values 0 or 1 according to the conventions of the current target.
  1105.  
  1106.    PRUNE_HINT contains flags to assist pruning of the search tree.  */
  1107.  
  1108. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1109. void
  1110. synth(insn_t *sequence,
  1111.       int n_insns,
  1112.       word *values,
  1113.       int n_values,
  1114.       word goal_value,
  1115.       int allowed_cost,
  1116.       int ci,
  1117.       int prune_hint)
  1118. {
  1119.   int s1, s2;
  1120.   word v, r1, r2;
  1121.   int co;
  1122.   int last_dest;
  1123.  
  1124. #ifdef TIMING
  1125.   int time_start = cputime();
  1126. #endif
  1127.  
  1128.   if (n_insns > 0)
  1129.     last_dest = sequence[n_insns - 1].d;
  1130.   else
  1131.     last_dest = -1;
  1132.  
  1133.   /* Binary operations with carry-in.  */
  1134.   if (ci >= 0 && flag_use_carry)
  1135.     {
  1136.       for (s1 = n_values - 1; s1 >= 0; s1--)
  1137.     {
  1138.       r1 = values[s1];
  1139.       for (s2 = s1 - 1; s2 >= 0; s2--)
  1140.         {
  1141.           r2 = values[s2];
  1142.  
  1143.           if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
  1144.         {
  1145.           /* We are in a leaf node.  CY was not set (to 0, 1 or to
  1146.              a data dependent value) by the previous insn.
  1147.  
  1148.              So one of the input operands has to be the result
  1149.              operand of the previous insn for that insn to be
  1150.              meaningful.  */
  1151.           if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
  1152.             continue;
  1153.         }
  1154.  
  1155. #if SPARC || RS6000 || M88000 || AM29K
  1156.           /* sparc:        addxcc
  1157.          rs6000:    ae
  1158.          m88000:    addu.cio
  1159.          am29k:        addc */
  1160.           PERFORM_ADD_CIO(v, co, r1, r2, ci);
  1161.           RECURSE(ADD_CIO, s1, s2, CY_JUST_SET);
  1162. #endif
  1163. #if SPARC || M88000
  1164.           /* sparc:        addx
  1165.          m88000:    addu.ci */
  1166.           PERFORM_ADD_CI(v, co, r1, r2, ci);
  1167.           RECURSE(ADD_CI, s1, s2, prune_hint & ~CY_JUST_SET);
  1168. #endif
  1169. #if SPARC
  1170.           /* sparc:        subxcc */
  1171.           PERFORM_SUB_CIO(v, co, r1, r2, ci);
  1172.           RECURSE(SUB_CIO, s1, s2, CY_JUST_SET);
  1173.           PERFORM_SUB_CIO(v, co, r2, r1, ci);
  1174.           RECURSE(SUB_CIO, s2, s1, CY_JUST_SET);
  1175. #endif
  1176. #if SPARC
  1177.           /* sparc:        subx */
  1178.           PERFORM_SUB_CI(v, co, r1, r2, ci);
  1179.           RECURSE(SUB_CI, s1, s2, prune_hint & ~CY_JUST_SET);
  1180.           PERFORM_SUB_CI(v, co, r2, r1, ci);
  1181.           RECURSE(SUB_CI, s2, s1, prune_hint & ~CY_JUST_SET);
  1182. #endif
  1183. #if RS6000 || M88000 || AM29K
  1184.           /* rs6000:    sfe
  1185.          m88000:    subu.cio
  1186.          am29k:        subc */
  1187.           PERFORM_ADC_CIO(v, co, r1, r2, ci);
  1188.           RECURSE(ADC_CIO, s1, s2, CY_JUST_SET);
  1189.           PERFORM_ADC_CIO(v, co, r2, r1, ci);
  1190.           RECURSE(ADC_CIO, s2, s1, CY_JUST_SET);
  1191. #endif
  1192. #if M88000
  1193.           /* m88000:    subu.ci */
  1194.           PERFORM_ADC_CI(v, co, r1, r2, ci);
  1195.           RECURSE(ADC_CI, s1, s2, prune_hint & ~CY_JUST_SET);
  1196.           PERFORM_ADC_CI(v, co, r2, r1, ci);
  1197.           RECURSE(ADC_CI, s2, s1, prune_hint & ~CY_JUST_SET);
  1198. #endif
  1199.         }
  1200.     }
  1201.     }
  1202.  
  1203.   /* Binary operations without carry-in.  */
  1204.   for (s1 = n_values - 1; s1 >= 0; s1--)
  1205.     {
  1206.       r1 = values[s1];
  1207.       for (s2 = s1 - 1; s2 >= 0; s2--)
  1208.     {
  1209.       r2 = values[s2];
  1210.  
  1211.       if (allowed_cost <= 1)
  1212.         {
  1213.           /* We are in a leaf node.
  1214.  
  1215.          So one of the input operands has to be the result operand
  1216.          of the previous insn for that insn to be meaningful.  */
  1217.           if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
  1218.         continue;
  1219.         }
  1220.  
  1221. #ifdef DM
  1222.       PERFORM_UMULWIDEN_HI(v, co, r1, r2, ci);
  1223.       RECURSE(UMULWIDEN_HI, s1, s2, prune_hint & ~CY_JUST_SET);
  1224. #endif
  1225. #if defined (DM) || defined (MM)
  1226.       PERFORM_MUL(v, co, r1, r2, ci);
  1227.       RECURSE(MUL, s1, s2, prune_hint & ~CY_JUST_SET);
  1228. #endif
  1229. #ifdef UDIV_WITH_SDIV
  1230.       PERFORM_SDIV (v, co, r1, r2, ci);
  1231.       RECURSE(SDIV, s1, s2, prune_hint & ~CY_JUST_SET);
  1232. #endif
  1233. #if SPARC || RS6000 || M88000 || AM29K
  1234.       /* sparc:    addcc
  1235.          rs6000:    a
  1236.          m88000:    addu.co
  1237.          am29k:    add */
  1238.       PERFORM_ADD_CO(v, co, r1, r2, ci);
  1239.       RECURSE(ADD_CO, s1, s2, CY_JUST_SET);
  1240. #endif
  1241. #if SPARC || RS6000 || M88000 || ALPHA
  1242.       /* sparc:    add
  1243.          rs6000:    cax
  1244.          m88000:    addu
  1245.          alpha:    addq */
  1246.       PERFORM_ADD(v, co, r1, r2, ci);
  1247.       RECURSE(ADD, s1, s2, prune_hint & ~CY_JUST_SET);
  1248. #endif
  1249. #if SPARC
  1250.       /* sparc:    subcc */
  1251.       PERFORM_SUB_CO(v, co, r1, r2, ci);
  1252.       RECURSE(SUB_CO, s1, s2, CY_JUST_SET);
  1253.       PERFORM_SUB_CO(v, co, r2, r1, ci);
  1254.       RECURSE(SUB_CO, s2, s1, CY_JUST_SET);
  1255. #endif
  1256. #if SPARC || M88000 || ALPHA
  1257.       /* sparc:    sub
  1258.          m88000:    subu
  1259.          alpha:    subq */
  1260.       PERFORM_SUB(v, co, r1, r2, ci);
  1261.       RECURSE(SUB, s1, s2, prune_hint & ~CY_JUST_SET);
  1262.       PERFORM_SUB(v, co, r2, r1, ci);
  1263.       RECURSE(SUB, s2, s1, prune_hint & ~CY_JUST_SET);
  1264. #endif
  1265. #if RS6000 || M88000 || AM29K
  1266.       /* rs6000:    sf
  1267.          m88000:    subu.co
  1268.          am29k:    sub */
  1269.       PERFORM_ADC_CO(v, co, r1, r2, ci);
  1270.       RECURSE(ADC_CO, s1, s2, CY_JUST_SET);
  1271.       PERFORM_ADC_CO(v, co, r2, r1, ci);
  1272.       RECURSE(ADC_CO, s2, s1, CY_JUST_SET);
  1273. #endif
  1274. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1275.       PERFORM_AND(v, co, r1, r2, ci);
  1276.       RECURSE(AND, s1, s2, prune_hint & ~CY_JUST_SET);
  1277.  
  1278.       PERFORM_IOR(v, co, r1, r2, ci);
  1279.       RECURSE(IOR, s1, s2, prune_hint & ~CY_JUST_SET);
  1280.  
  1281.       PERFORM_XOR(v, co, r1, r2, ci);
  1282.       RECURSE(XOR, s1, s2, prune_hint & ~CY_JUST_SET);
  1283.  
  1284.       PERFORM_ANDC(v, co, r1, r2, ci);
  1285.       RECURSE(ANDC, s1, s2, prune_hint & ~CY_JUST_SET);
  1286.       PERFORM_ANDC(v, co, r2, r1, ci);
  1287.       RECURSE(ANDC, s2, s1, prune_hint & ~CY_JUST_SET);
  1288. #endif
  1289. #if SPARC || RS6000 || M88000 || ALPHA
  1290.       PERFORM_IORC(v, co, r1, r2, ci);
  1291.       RECURSE(IORC, s1, s2, prune_hint & ~CY_JUST_SET);
  1292.       PERFORM_IORC(v, co, r2, r1, ci);
  1293.       RECURSE(IORC, s2, s1, prune_hint & ~CY_JUST_SET);
  1294. #endif
  1295. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1296.       PERFORM_EQV(v, co, r1, r2, ci);
  1297.       RECURSE(EQV, s1, s2, prune_hint & ~CY_JUST_SET);
  1298. #endif
  1299. #if RS6000 || AM29K
  1300.       PERFORM_NAND(v, co, r1, r2, ci);
  1301.       RECURSE(NAND, s1, s2, prune_hint & ~CY_JUST_SET);
  1302.  
  1303.       PERFORM_NOR(v, co, r1, r2, ci);
  1304.       RECURSE(NOR, s1, s2, prune_hint & ~CY_JUST_SET);
  1305. #endif
  1306. #if RS6000 && !defined (AVOID_DOZ)
  1307.       PERFORM_DOZ(v, co, r1, r2, ci);
  1308.       RECURSE(DOZ, s1, s2, prune_hint & ~CY_JUST_SET);
  1309.       PERFORM_DOZ(v, co, r2, r1, ci);
  1310.       RECURSE(DOZ, s2, s1, prune_hint & ~CY_JUST_SET);
  1311. #endif
  1312. #if AM29K
  1313.       PERFORM_CPEQ(v, co, r1, r2, ci);
  1314.       RECURSE(CPEQ, s1, s2, prune_hint & ~CY_JUST_SET);
  1315.       PERFORM_CPGE(v, co, r1, r2, ci);
  1316.       RECURSE(CPGE, s1, s2, prune_hint & ~CY_JUST_SET);
  1317.       PERFORM_CPGEU(v, co, r1, r2, ci);
  1318.       RECURSE(CPGEU, s1, s2, prune_hint & ~CY_JUST_SET);
  1319.       PERFORM_CPGT(v, co, r1, r2, ci);
  1320.       RECURSE(CPGT, s1, s2, prune_hint & ~CY_JUST_SET);
  1321.       PERFORM_CPGTU(v, co, r1, r2, ci);
  1322.       RECURSE(CPGTU, s1, s2, prune_hint & ~CY_JUST_SET);
  1323.       PERFORM_CPLE(v, co, r1, r2, ci);
  1324.       RECURSE(CPLE, s1, s2, prune_hint & ~CY_JUST_SET);
  1325.       PERFORM_CPLEU(v, co, r1, r2, ci);
  1326.       RECURSE(CPLEU, s1, s2, prune_hint & ~CY_JUST_SET);
  1327.       PERFORM_CPLT(v, co, r1, r2, ci);
  1328.       RECURSE(CPLT, s1, s2, prune_hint & ~CY_JUST_SET);
  1329.       PERFORM_CPLTU(v, co, r1, r2, ci);
  1330.       RECURSE(CPLTU, s1, s2, prune_hint & ~CY_JUST_SET);
  1331.       PERFORM_CPNEQ(v, co, r1, r2, ci);
  1332.       RECURSE(CPNEQ, s1, s2, prune_hint & ~CY_JUST_SET);
  1333. #endif
  1334. #if ALPHA
  1335.       PERFORM_CMPEQ(v, co, r1, r2, ci);
  1336.       RECURSE(CMPEQ, s1, s2, prune_hint & ~CY_JUST_SET);
  1337.  
  1338.       PERFORM_CMPLE(v, co, r1, r2, ci);
  1339.       RECURSE(CMPLE, s1, s2, prune_hint & ~CY_JUST_SET);
  1340.       PERFORM_CMPLE(v, co, r2, r1, ci);
  1341.       RECURSE(CMPLE, s2, s1, prune_hint & ~CY_JUST_SET);
  1342.  
  1343.       PERFORM_CMPLEU(v, co, r1, r2, ci);
  1344.       RECURSE(CMPLEU, s1, s2, prune_hint & ~CY_JUST_SET);
  1345.       PERFORM_CMPLEU(v, co, r2, r1, ci);
  1346.       RECURSE(CMPLEU, s2, s1, prune_hint & ~CY_JUST_SET);
  1347.  
  1348.       PERFORM_CMPLT(v, co, r1, r2, ci);
  1349.       RECURSE(CMPLT, s1, s2, prune_hint & ~CY_JUST_SET);
  1350.       PERFORM_CMPLT(v, co, r2, r1, ci);
  1351.       RECURSE(CMPLT, s2, s1, prune_hint & ~CY_JUST_SET);
  1352.  
  1353.       PERFORM_CMPLTU(v, co, r1, r2, ci);
  1354.       RECURSE(CMPLTU, s1, s2, prune_hint & ~CY_JUST_SET);
  1355.       PERFORM_CMPLTU(v, co, r2, r1, ci);
  1356.       RECURSE(CMPLTU, s2, s1, prune_hint & ~CY_JUST_SET);
  1357. #endif
  1358. #if M88000
  1359.       PERFORM_CMPPAR (v, co, r1, r2, ci);
  1360.       RECURSE(CMPPAR, s1, s2, prune_hint & ~CY_JUST_SET);
  1361.       PERFORM_CMPPAR (v, co, r2, r1, ci);
  1362.       RECURSE(CMPPAR, s2, s1, prune_hint & ~CY_JUST_SET);
  1363. #endif
  1364.     }
  1365.     }
  1366.  
  1367.   /* Unary operations with carry-in.  */
  1368.   if (ci >= 0 && flag_use_carry)
  1369.     {
  1370.       for (s1 = n_values - 1; s1 >= 0; s1--)
  1371.     {
  1372.       r1 = values[s1];
  1373.  
  1374.       if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
  1375.         {
  1376.           /* We are in a leaf node and CY was not set (to 1 or to a
  1377.          data dependent value) by the previous insn.
  1378.  
  1379.          The input operand has to be the result operand of the
  1380.          previous insn for that insn to be meaningful.  */
  1381.           if (last_dest >= 0 && s1 != last_dest)
  1382.         continue;
  1383.         }
  1384.  
  1385. #if SPARC || RS6000 || M88000 || AM29K
  1386.       /* d,cy = 2*r1 + cy
  1387.          sparc:    addxcc    s1,s1,d
  1388.          rs6000:    ae    d,s1,s1
  1389.          m88000:    addu.cio d,s1,s1
  1390.          am29k:        addc    d,s1,s1 */
  1391.       PERFORM_ADD_CIO(v, co, r1, r1, ci);
  1392.       RECURSE(ADD_CIO, s1, s1, CY_JUST_SET);
  1393. #endif
  1394. #if SPARC || M88000 
  1395.       /* d = 2*r1 + cy
  1396.          sparc:    addx    s1,s1,d
  1397.          m88000:    addu.ci    d,s1,s1  */
  1398.       PERFORM_ADD_CI(v, co, r1, r1, ci);
  1399.       RECURSE(ADD_CI, s1, s1, prune_hint & ~CY_JUST_SET);
  1400. #endif
  1401. #if SPARC || RS6000 || M88000 || AM29K
  1402.       /* d,cy = r1 + cy - 1
  1403.          sparc:    addxcc    s1,-1,d
  1404.          rs6000:    ame    d,s1
  1405.          m88000:    subu.cio d,s1,r0
  1406.          am29k:    subc    d,s1,0 */
  1407.       PERFORM_ADD_CIO(v, co, r1, VALUE(-1), ci);
  1408.       RECURSE(ADD_CIO, s1, CNST(-1), CY_JUST_SET);
  1409. #endif
  1410. #if SPARC || RS6000 || M88000 || AM29K
  1411.       /* d,cy = r1 + cy
  1412.          sparc:    addxcc    s1,0,d
  1413.          rs6000:    aze    d,s1
  1414.          m88000:    addu.cio d,s1,r0
  1415.          am29k:    addc    d,s1,0 */
  1416.       PERFORM_ADD_CIO(v, co, r1, VALUE(0), ci);
  1417.       RECURSE(ADD_CIO, s1, CNST(0), CY_JUST_SET);
  1418. #endif
  1419. #if SPARC
  1420.       /* d,cy = 0 - r1 - cy
  1421.          sparc:     subxcc    %g0,s1,d */
  1422.       PERFORM_SUB_CIO(v, co, VALUE(0), r1, ci);
  1423.       RECURSE(SUB_CIO, CNST(0), s1, CY_JUST_SET);
  1424. #endif
  1425. #if SPARC
  1426.       /* d = r1 + 1 - cy
  1427.          sparc:     subx    s1,-1,d */
  1428.       PERFORM_SUB_CI(v, co, r1, VALUE(-1), ci);
  1429.       RECURSE(SUB_CI, s1, CNST(-1), prune_hint & ~CY_JUST_SET);
  1430. #endif
  1431. #if SPARC
  1432.       /* d,cy = r1 + 1 - cy
  1433.          sparc:     subxcc    s1,-1,d */
  1434.       PERFORM_SUB_CIO(v, co, r1, VALUE(-1), ci);
  1435.       RECURSE(SUB_CIO, s1, CNST(-1), CY_JUST_SET);
  1436. #endif
  1437. #if RS6000
  1438.       /* d,cy = -1 + ~r1 + cy
  1439.          rs6000:    sfme    d,s1 */
  1440.       PERFORM_ADC_CIO(v, co, VALUE(-1), r1, ci);
  1441.       RECURSE(ADC_CIO, CNST(-1), s1, CY_JUST_SET);
  1442. #endif
  1443. #if RS6000 || M88000 || AM29K
  1444.       /* d,cy = ~r1 + cy
  1445.          m88000:    subu.cio d,r0,s1
  1446.          rs6000:    sfze    d,s1
  1447.          am29k:    subrc    d,s1,0 */
  1448.       PERFORM_ADC_CIO(v, co, VALUE(0), r1, ci);
  1449.       RECURSE(ADC_CIO, CNST(0), s1, CY_JUST_SET);
  1450. #endif
  1451.     }
  1452.     }
  1453.  
  1454.   /* Unary operations without carry-in.  */
  1455.   for (s1 = n_values - 1; s1 >= 0; s1--)
  1456.     {
  1457.       r1 = values[s1];
  1458.  
  1459.       if (allowed_cost <= 1)
  1460.     {
  1461.       /* We are in a leaf node.
  1462.  
  1463.          The input operand has to be the result operand of the
  1464.          previous insns for that insn to be meaningful.  */
  1465.       if (last_dest >= 0 && s1 != last_dest)
  1466.         continue;
  1467.     }
  1468.  
  1469. #ifdef DM
  1470.       PERFORM_INVDIV(v, co, r1, ci);
  1471.       RECURSE(INVDIV, s1, 0, prune_hint & ~CY_JUST_SET);
  1472.  
  1473.       PERFORM_INVMOD(v, co, r1, ci);
  1474.       RECURSE(INVMOD, s1, 0, prune_hint & ~CY_JUST_SET);
  1475. #endif
  1476. #if SPARC || RS6000 || M88000 || AM29K
  1477.       /* d,cy = 2*r1
  1478.      sparc:        addcc    s1,s1,d
  1479.      rs6000:    a    d,s1,s1
  1480.      m88000:    addu.co    d,s1,s1
  1481.      am29k:        add    d,s1,s1 */
  1482.       PERFORM_ADD_CO(v, co, r1, r1, ci);
  1483.       RECURSE(ADD_CO, s1, s1, CY_JUST_SET);
  1484. #endif
  1485. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1486.       /* d = r1 & 1
  1487.      sparc:        and    s1,1,d
  1488.      rs6000:    rlinm    d,s1,0,31,31
  1489.      m88000:    mask    d,s1,1
  1490.      am29k:        and    d,s1,1
  1491.      alpha:        and    s1,1,d */
  1492.       PERFORM_AND(v, co, r1, VALUE(1), ci);
  1493.       RECURSE(AND, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1494. #endif
  1495. #if RS6000 || M88000
  1496.       /* d = r1 & 0x80000000
  1497.      rs6000:    rlinm    d,s1,0,0,0
  1498.      m88000:    mask.u    d,s1,0x8000 */
  1499.       PERFORM_AND(v, co, r1, VALUE_MIN_SIGNED, ci);
  1500.       RECURSE(AND, s1, CNST_0x80000000, prune_hint & ~CY_JUST_SET);
  1501.  
  1502.       /* d = r1 & 0x7fffffff
  1503.      rs6000:    rlinm    d,s1,0,1,31
  1504.      m88000:    and.u    d,s1,0x7fff */
  1505.       PERFORM_AND(v, co, r1, VALUE_MAX_SIGNED, ci);
  1506.       RECURSE(AND, s1, CNST_0x7FFFFFFF, prune_hint & ~CY_JUST_SET);
  1507. #endif
  1508. #if RS6000 || M88000
  1509.       PERFORM_XOR(v, co, r1, VALUE_MIN_SIGNED, ci);
  1510.       RECURSE(XOR, s1, CNST_0x80000000, prune_hint & ~CY_JUST_SET);
  1511.  
  1512.       PERFORM_IOR(v, co, r1, VALUE_MIN_SIGNED, ci);
  1513.       RECURSE(IOR, s1, CNST_0x80000000, prune_hint & ~CY_JUST_SET);
  1514. #endif
  1515. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1516.       /* d = r1 ^ 1
  1517.      sparc:        xor    s1,1,d
  1518.      rs6000:    xoril    d,s1,1
  1519.      m88000:    xor    d,s1,1
  1520.      am29k:        xor    d,s1,1
  1521.      alpha:        xor    s1,1,d */
  1522.       PERFORM_XOR(v, co, r1, VALUE(1), ci);
  1523.       RECURSE(XOR, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1524. #endif
  1525. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1526.       /* d = ~r1
  1527.      sparc:        xnor    %g0,s1,d
  1528.      rs6000:    nand    d,s1,s1
  1529.      m88000:    xor.c    d,s1,r0
  1530.      am29k:        nand    d,s1,s1
  1531.      alpha:        ornot    $31,s1,d */
  1532.       PERFORM_SUB(v, co, VALUE(-1), r1, ci);
  1533.       RECURSE(SUB, CNST(-1), s1, prune_hint & ~CY_JUST_SET);
  1534. #endif
  1535. #if RS6000
  1536.       /* d,cy = -1 + ~r1 (i.e. one's complement and set carry.)
  1537.      rs6000:    sfi    d,s1,-1 */
  1538.       PERFORM_ADC_CO(v, co, VALUE(-1), r1, ci);
  1539.       RECURSE(ADC_CO, CNST(-1), s1, CY_JUST_SET | CY_1);
  1540. #endif
  1541. #if SPARC || RS6000 || AM29K
  1542.       /* d,cy = r1 + 1
  1543.      sparc:        addcc    s1,1,d
  1544.      rs6000:    ai    d,s1,1
  1545.      am29k:        add    d,s1,1 */
  1546.       PERFORM_ADD_CO(v, co, r1, VALUE(1), ci);
  1547.       RECURSE(ADD_CO, s1, CNST(1), CY_JUST_SET);
  1548. #endif
  1549. #if SPARC || RS6000 || M88000 || ALPHA
  1550.       /* d = r1 + 1
  1551.      sparc:        add    s1,1,d
  1552.      rs6000:    cal    d,1(s1)
  1553.      m88000:    addu    d,s1,1
  1554.      alpha:        addq    s1,1,d */
  1555.       PERFORM_ADD(v, co, r1, VALUE(1), ci);
  1556.       RECURSE(ADD, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1557. #endif
  1558. #if 0 && RS6000 /* This has the same effect as a "xoriu". */
  1559.       /* d = r1 + 0x80000000
  1560.      rs6000:    cau    d,s1,0x8000 */
  1561.       PERFORM_ADD(v, co, r1, VALUE_MIN_SIGNED, ci);
  1562.       RECURSE(ADD, s1, CNST_0x80000000, CY_JUST_SET);
  1563. #endif
  1564. #if SPARC || RS6000 || AM29K /* not M88000 */
  1565.       /* d,cy = r1 + -1
  1566.      sparc:        addcc    s1,-1,d
  1567.      rs6000:    ai    d,s1,-1
  1568.      am29k:        sub    d,s1,1 */
  1569.       PERFORM_ADD_CO(v, co, r1, VALUE(-1), ci);
  1570.       RECURSE(ADD_CO, s1, CNST(-1), CY_JUST_SET);
  1571. #endif
  1572. #if SPARC
  1573.       /* d,cy = r1 - 1. [This isn't redundant, in spite we add -1 above.]
  1574.      sparc:        subcc    s1,1,d */
  1575.       PERFORM_SUB_CO(v, co, r1, VALUE(1), ci);
  1576.       RECURSE(SUB_CO, s1, CNST(1), CY_JUST_SET);
  1577. #endif
  1578. #if SPARC
  1579.       /* d,cy = -r1
  1580.      sparc:        subcc    %g0,s1,d */
  1581.       PERFORM_SUB_CO(v, co, VALUE(0), r1, ci);
  1582.       RECURSE(SUB_CO, CNST(0), s1, CY_JUST_SET);
  1583. #endif
  1584. #if SPARC || RS6000 || M88000 || ALPHA
  1585.       /* d = -r1
  1586.      sparc:        sub    %g0,s1,d
  1587.      rs6000:    neg    d,s1
  1588.      m88000:    subu    d,r0,s1
  1589.      alpha:        subq    $31,s1,d */
  1590.       PERFORM_SUB(v, co, VALUE(0), r1, ci);
  1591.       RECURSE(SUB, CNST(0), s1, prune_hint & ~CY_JUST_SET);
  1592. #endif
  1593. #if RS6000 || M88000 || AM29K
  1594.       /* d,cy = -r1
  1595.      rs6000:    sf    d,s1,0
  1596.      m88000:    subu.co    d,r0,s1
  1597.      am29k:        subr    d,s1,0 */
  1598.       PERFORM_ADC_CO(v, co, VALUE(0), r1, ci);
  1599.       RECURSE(ADC_CO, CNST(0), s1, CY_JUST_SET);
  1600. #endif
  1601. #if RS6000
  1602.       /* d = abs(r1)
  1603.      rs6000:    abs    d,s1 */
  1604.       PERFORM_ABSVAL(v, co, r1, ci);
  1605.       RECURSE(ABSVAL, s1, 0, prune_hint & ~CY_JUST_SET);
  1606.  
  1607.       /* d = -abs(r1)
  1608.      rs6000:    nabs    d,s1 */
  1609.       PERFORM_NABSVAL(v, co, r1, ci);
  1610.       RECURSE(NABSVAL, s1, 0, prune_hint & ~CY_JUST_SET);
  1611. #endif
  1612. #if RS6000 && !defined (AVOID_DOZ)
  1613.       PERFORM_DOZ(v, co, VALUE(0), r1, ci);
  1614.       RECURSE(DOZ, CNST(0), s1, prune_hint & ~CY_JUST_SET);
  1615.       PERFORM_DOZ(v, co, VALUE(-1), r1, ci);
  1616.       RECURSE(DOZ, CNST(-1), s1, prune_hint & ~CY_JUST_SET);
  1617. #endif
  1618. #if SHIFTS
  1619.       {
  1620.     int cnt;
  1621.     for (cnt = 1; cnt < BITS_PER_WORD; cnt++)
  1622.       {
  1623. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1624.         PERFORM_LSHIFTR(v, co, r1, VALUE(cnt), ci);
  1625.         RECURSE(LSHIFTR, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1626. #endif
  1627. #if SPARC || M88000 || AM29K || ALPHA
  1628.         PERFORM_ASHIFTR(v, co, r1, VALUE(cnt), ci);
  1629.         RECURSE(ASHIFTR, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1630. #endif
  1631. #if RS6000
  1632.         PERFORM_ASHIFTR_CON(v, co, r1, VALUE(cnt), ci);
  1633.         RECURSE(ASHIFTR_CON, s1, CNST(cnt), CY_JUST_SET);
  1634. #endif
  1635. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1636.         PERFORM_SHIFTL(v, co, r1, VALUE(cnt), ci);
  1637.         RECURSE(SHIFTL, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1638. #endif
  1639. #if RS6000 || M88000
  1640.         PERFORM_ROTATEL(v, co, r1, VALUE(cnt), ci);
  1641.         RECURSE(ROTATEL, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1642. #endif
  1643.       }
  1644.       }
  1645. #else
  1646. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1647.       PERFORM_LSHIFTR(v, co, r1, VALUE(1), ci);
  1648.       RECURSE(LSHIFTR, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1649. #endif
  1650. #if SPARC || M88000 || AM29K || ALPHA
  1651.       PERFORM_ASHIFTR(v, co, r1, VALUE(1), ci);
  1652.       RECURSE(ASHIFTR, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1653. #endif
  1654. #if RS6000
  1655.       PERFORM_ASHIFTR_CON(v, co, r1, VALUE(1), ci);
  1656.       RECURSE(ASHIFTR_CON, s1, CNST(1), CY_JUST_SET);
  1657. #endif
  1658. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1659.       PERFORM_SHIFTL(v, co, r1, VALUE(1), ci);
  1660.       RECURSE(SHIFTL, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1661. #endif
  1662. #if RS6000 || M88000
  1663.       PERFORM_ROTATEL(v, co, r1, VALUE(1), ci);
  1664.       RECURSE(ROTATEL, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  1665. #endif
  1666. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1667.       PERFORM_LSHIFTR(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  1668.       RECURSE(LSHIFTR, s1, CNST(BITS_PER_WORD-1), prune_hint & ~CY_JUST_SET);
  1669. #endif
  1670. #if SPARC || M88000 || AM29K || ALPHA
  1671.       PERFORM_ASHIFTR(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  1672.       RECURSE(ASHIFTR, s1, CNST(BITS_PER_WORD-1), prune_hint & ~CY_JUST_SET);
  1673. #endif
  1674. #if RS6000
  1675.       PERFORM_ASHIFTR_CON(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  1676.       RECURSE(ASHIFTR_CON, s1, CNST(BITS_PER_WORD-1), CY_JUST_SET);
  1677. #endif
  1678. #if SHIFT16
  1679. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1680.       PERFORM_LSHIFTR(v, co, r1, VALUE(16), ci);
  1681.       RECURSE(LSHIFTR, s1, CNST(16), prune_hint & ~CY_JUST_SET);
  1682. #endif
  1683. #if SPARC || M88000 || AM29K || ALPHA
  1684.       PERFORM_ASHIFTR(v, co, r1, VALUE(16), ci);
  1685.       RECURSE(ASHIFTR, s1, CNST(16), prune_hint & ~CY_JUST_SET);
  1686. #endif
  1687. #if RS6000
  1688.       PERFORM_ASHIFTR_CON(v, co, r1, VALUE(16), ci);
  1689.       RECURSE(ASHIFTR_CON, s1, CNST(16), CY_JUST_SET);
  1690. #endif
  1691. #if SPARC || RS6000 || M88000 || AM29K || ALPHA
  1692.       PERFORM_SHIFTL(v, co, r1, VALUE(16), ci);
  1693.       RECURSE(SHIFTL, s1, CNST(16), prune_hint & ~CY_JUST_SET);
  1694. #endif
  1695. #if RS6000 || M88000
  1696.       PERFORM_ROTATEL(v, co, r1, VALUE(16), ci);
  1697.       RECURSE(ROTATEL, s1, CNST(16), prune_hint & ~CY_JUST_SET);
  1698. #endif
  1699. #endif /* SHIFT16 */
  1700. #endif /* SHIFTS */
  1701. #if EXTRACTS
  1702.       {
  1703.     int cnt;
  1704.     for (cnt = 1; cnt < BITS_PER_WORD; cnt++)
  1705.       {
  1706. #if M88000
  1707.         PERFORM_EXTS1(v, co, r1, VALUE(cnt), ci);
  1708.         RECURSE(EXTS1, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1709.         PERFORM_EXTU1(v, co, r1, VALUE(cnt), ci);
  1710.         RECURSE(EXTU1, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1711.         PERFORM_EXTS2(v, co, r1, VALUE(cnt), ci);
  1712.         RECURSE(EXTS2, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1713.         PERFORM_EXTU2(v, co, r1, VALUE(cnt), ci);
  1714.         RECURSE(EXTU2, s1, CNST(cnt), prune_hint & ~CY_JUST_SET);
  1715. #endif
  1716.       }
  1717.       }
  1718. #endif
  1719. #if AM29K
  1720.       PERFORM_CPEQ(v, co, r1, VALUE(0), ci);
  1721.       RECURSE(CPEQ, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1722.       PERFORM_CPGE(v, co, r1, VALUE(0), ci);
  1723.       RECURSE(CPGE, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1724.       PERFORM_CPGEU(v, co, r1, VALUE(0), ci);
  1725.       RECURSE(CPGEU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1726.       PERFORM_CPGT(v, co, r1, VALUE(0), ci);
  1727.       RECURSE(CPGT, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1728.       PERFORM_CPGTU(v, co, r1, VALUE(0), ci);
  1729.       RECURSE(CPGTU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1730.       PERFORM_CPLE(v, co, r1, VALUE(0), ci);
  1731.       RECURSE(CPLE, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1732.       PERFORM_CPLEU(v, co, r1, VALUE(0), ci);
  1733.       RECURSE(CPLEU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1734.       PERFORM_CPLT(v, co, r1, VALUE(0), ci);
  1735.       RECURSE(CPLT, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1736.       PERFORM_CPLTU(v, co, r1, VALUE(0), ci);
  1737.       RECURSE(CPLTU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1738.       PERFORM_CPNEQ(v, co, r1, VALUE(0), ci);
  1739.       RECURSE(CPNEQ, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1740. #endif
  1741. #if ALPHA
  1742.       PERFORM_CMPEQ(v, co, r1, VALUE(0), ci);
  1743.       RECURSE(CMPEQ, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1744.  
  1745.       PERFORM_CMPLE(v, co, r1, VALUE(0), ci);
  1746.       RECURSE(CMPLE, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1747.       PERFORM_CMPLE(v, co, VALUE(0), r1, ci);
  1748.       RECURSE(CMPLE, CNST(0), s1, prune_hint & ~CY_JUST_SET);
  1749.  
  1750.       PERFORM_CMPLEU(v, co, r1, VALUE(0), ci);
  1751.       RECURSE(CMPLEU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1752.       PERFORM_CMPLEU(v, co, VALUE(0), r1, ci);
  1753.       RECURSE(CMPLEU, CNST(0), s1, prune_hint & ~CY_JUST_SET);
  1754.  
  1755.       PERFORM_CMPLT(v, co, r1, VALUE(0), ci);
  1756.       RECURSE(CMPLT, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1757.       PERFORM_CMPLT(v, co, VALUE(0), r1, ci);
  1758.       RECURSE(CMPLT, CNST(0), s1, prune_hint & ~CY_JUST_SET);
  1759.  
  1760.       PERFORM_CMPLTU(v, co, r1, VALUE(0), ci);
  1761.       RECURSE(CMPLTU, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1762.       PERFORM_CMPLTU(v, co, VALUE(0), r1, ci);
  1763.       RECURSE(CMPLTU, CNST(0), s1, prune_hint & ~CY_JUST_SET);
  1764. #endif
  1765. #if RS6000 || AM29K
  1766.       PERFORM_CLZ(v, co, r1, ci);
  1767.       RECURSE(CLZ, s1, 0, prune_hint & ~CY_JUST_SET);
  1768. #endif
  1769. #if M88000
  1770.       PERFORM_FF1(v, co, r1, ci);
  1771.       RECURSE(FF1, s1, 0, prune_hint & ~CY_JUST_SET);
  1772. #endif
  1773. #if M88000
  1774.       PERFORM_CMPPAR (v, co, r1, VALUE(0), ci);
  1775.       RECURSE(CMPPAR, s1, CNST(0), prune_hint & ~CY_JUST_SET);
  1776.       PERFORM_CMPPAR (v, co, VALUE(0), r1, ci);
  1777.       RECURSE(CMPPAR, CNST(0), s1, prune_hint & ~CY_JUST_SET);
  1778. #endif
  1779.     }
  1780.  
  1781. #if ALPHA
  1782.   /* Alpha Conditional move instructions need special treatment.  We let all
  1783.      other instructions assign the next higher-numbered register, but we
  1784.      can't do that here since cmov insns leave the register undefined if the
  1785.      instruction condition is not satisfied.  Instead we let the cmov
  1786.      instructions non-deterministically overwrite all already-defined
  1787.      registers.  */
  1788.   for (s1 = n_values - 1; s1 >= 0; s1--)
  1789.     {
  1790.       r1 = values[s1];
  1791.       for (s2 = s1 - 1; s2 >= 0; s2--)
  1792.     {
  1793.       int dr;
  1794.       r2 = values[s2];
  1795.  
  1796.       if (allowed_cost <= 1)
  1797.         {
  1798.           /* We are in a leaf node.  */
  1799.  
  1800.           /* One of the input operands has to be the result operand
  1801.          of the previous insn for that insn to be meaningful.  */
  1802.           if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
  1803.         continue;
  1804.         }
  1805.  
  1806.       for (dr = n_values - 1; dr >= 0; dr--)
  1807.         {
  1808.           v = values[dr];
  1809.  
  1810.           PERFORM_CMOVEQ (v, co, r1, r2, ci);
  1811.           CRECURSE_2OP(CMOVEQ, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  1812.           PERFORM_CMOVEQ (v, co, r2, r1, ci);
  1813.           CRECURSE_2OP(CMOVEQ, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);
  1814.  
  1815.           PERFORM_CMOVNE (v, co, r1, r2, ci);
  1816.           CRECURSE_2OP(CMOVNE, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  1817.           PERFORM_CMOVNE (v, co, r2, r1, ci);
  1818.           CRECURSE_2OP(CMOVNE, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);
  1819.  
  1820.           PERFORM_CMOVLT (v, co, r1, r2, ci);
  1821.           CRECURSE_2OP(CMOVLT, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  1822.           PERFORM_CMOVLT (v, co, r2, r1, ci);
  1823.           CRECURSE_2OP(CMOVLT, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);
  1824.  
  1825.           PERFORM_CMOVGE (v, co, r1, r2, ci);
  1826.           CRECURSE_2OP(CMOVGE, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  1827.           PERFORM_CMOVGE (v, co, r2, r1, ci);
  1828.           CRECURSE_2OP(CMOVGE, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);
  1829.  
  1830.           PERFORM_CMOVLE (v, co, r1, r2, ci);
  1831.           CRECURSE_2OP(CMOVLE, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  1832.           PERFORM_CMOVLE (v, co, r2, r1, ci);
  1833.           CRECURSE_2OP(CMOVLE, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);
  1834.  
  1835.           PERFORM_CMOVGT (v, co, r1, r2, ci);
  1836.           CRECURSE_2OP(CMOVGT, dr, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  1837.           PERFORM_CMOVGT (v, co, r2, r1, ci);
  1838.           CRECURSE_2OP(CMOVGT, dr, s2, s1, 1, prune_hint & ~CY_JUST_SET);
  1839.         }
  1840.     }
  1841.     }
  1842.  
  1843.   for (s1 = n_values - 1; s1 >= 0; s1--)
  1844.     {
  1845.       int dr;
  1846.       r1 = values[s1];
  1847.  
  1848.       if (allowed_cost <= 1)
  1849.     {
  1850.       /* We are in a leaf node.
  1851.  
  1852.          The input operand has to be the result operand of the
  1853.          previous insns for that insn to be meaningful.  */
  1854.       if (last_dest >= 0 && s1 != last_dest)
  1855.         continue;
  1856.     }
  1857.  
  1858.       for (dr = n_values - 1; dr >= 0; dr--)
  1859.     {
  1860.       v = values[dr];
  1861.  
  1862.       PERFORM_CMOVEQ (v, co, r1, VALUE(0), ci);
  1863.       CRECURSE_2OP(CMOVEQ, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
  1864.       PERFORM_CMOVEQ (v, co, VALUE(0), r1, ci);
  1865.       CRECURSE_2OP(CMOVEQ, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);
  1866.  
  1867.       PERFORM_CMOVNE (v, co, r1, VALUE(0), ci);
  1868.       CRECURSE_2OP(CMOVNE, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
  1869.       PERFORM_CMOVNE (v, co, VALUE(0), r1, ci);
  1870.       CRECURSE_2OP(CMOVNE, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);
  1871.  
  1872.       PERFORM_CMOVLT (v, co, r1, VALUE(0), ci);
  1873.       CRECURSE_2OP(CMOVLT, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
  1874.       PERFORM_CMOVLT (v, co, VALUE(0), r1, ci);
  1875.       CRECURSE_2OP(CMOVLT, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);
  1876.  
  1877.       PERFORM_CMOVGE (v, co, r1, VALUE(0), ci);
  1878.       CRECURSE_2OP(CMOVGE, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
  1879.       PERFORM_CMOVGE (v, co, VALUE(0), r1, ci);
  1880.       CRECURSE_2OP(CMOVGE, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);
  1881.  
  1882.       PERFORM_CMOVLE (v, co, r1, VALUE(0), ci);
  1883.       CRECURSE_2OP(CMOVLE, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
  1884.       PERFORM_CMOVLE (v, co, VALUE(0), r1, ci);
  1885.       CRECURSE_2OP(CMOVLE, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);
  1886.  
  1887.       PERFORM_CMOVGT (v, co, r1, VALUE(0), ci);
  1888.       CRECURSE_2OP(CMOVGT, dr, s1, CNST(0), 1, prune_hint & ~CY_JUST_SET);
  1889.       PERFORM_CMOVGT (v, co, VALUE(0), r1, ci);
  1890.       CRECURSE_2OP(CMOVGT, dr, CNST(0), s1, 1, prune_hint & ~CY_JUST_SET);
  1891.     }
  1892.     }
  1893. #endif /* ALPHA */
  1894.  
  1895.   /* 0-ary instructions, just dependent on carry.  */
  1896.   if (ci >= 0 && flag_use_carry
  1897.       && (allowed_cost <= 1 ? ((prune_hint & CY_JUST_SET) != 0) : 1))
  1898.     {
  1899.       /* We don't do "0 - 1 - cy" or "0 + 1 + cy" here.  It would
  1900.      probably give very few new sequences. */
  1901. #if SPARC || M88000
  1902.       /* d = cy.
  1903.      sparc:        addx    %g0,0,d
  1904.      m88000:    addu.ci d,r0,r0 */
  1905.       PERFORM_ADD_CI(v, co, VALUE(0), VALUE(0), ci);
  1906.       RECURSE(ADD_CI, CNST(0), CNST(0), prune_hint & ~CY_JUST_SET);
  1907. #endif
  1908. #if SPARC || M88000
  1909.       /* d = cy, cy = 0.
  1910.      sparc:        addxcc    %g0,0,d
  1911.      m88000:    addu.cio d,r0,r0 */
  1912.       PERFORM_ADD_CIO(v, co, VALUE(0), VALUE(0), ci);
  1913.       RECURSE(ADD_CIO, CNST(0), CNST(0), CY_JUST_SET | CY_0);
  1914. #endif
  1915. #if SPARC
  1916.       /* Using SUB_CIO instead would make no difference.
  1917.      It'd just set carry to it's old value.  */
  1918.       /* d = -cy.
  1919.      sparc:        subx    %g0,0,d */
  1920.       PERFORM_SUB_CI(v, co, VALUE(0), VALUE(0), ci);
  1921.       RECURSE(SUB_CI, CNST(0), CNST(0), prune_hint & ~CY_JUST_SET);
  1922. #endif
  1923. #if SPARC
  1924.       /* d = 1 - cy.
  1925.      sparc:        subx    %g0,-1,d */
  1926.       PERFORM_SUB_CI(v, co, VALUE(0), VALUE(-1), ci);
  1927.       RECURSE(SUB_CI, CNST(0), CNST(-1), CY_JUST_SET | CY_1);
  1928. #endif
  1929. #if SPARC
  1930.       /* d = 1 - cy, cy = 1.
  1931.      sparc:        subxcc    %g0,-1,d */
  1932.       PERFORM_SUB_CIO(v, co, VALUE(0), VALUE(-1), ci);
  1933.       RECURSE(SUB_CIO, CNST(0), CNST(-1), CY_JUST_SET | CY_1);
  1934. #endif
  1935. #if SPARC
  1936.       /* Using ADD_CIO instead would make no difference.
  1937.      It'd just set carry to it's old value.  */
  1938.       /* d = -1 + cy.
  1939.      sparc:        addx    %g0,-1,d */
  1940.       PERFORM_ADD_CI(v, co, VALUE(0), VALUE(-1), ci);
  1941.       RECURSE(ADD_CI, CNST(0), CNST(-1), prune_hint & ~CY_JUST_SET);
  1942. #endif
  1943. #if RS6000 || AM29K /* Use subu.ci on 88k instead with same result */
  1944.       /* d = -1 + cy, cy = cy
  1945.      rs6000:    sfe    d,d,d
  1946.      am29k:        subc    d,d,d */
  1947.       PERFORM_ADC_CIO(v, co, VALUE(0), VALUE(0), ci);
  1948.       RECURSE(ADC_CIO, n_values, n_values, prune_hint & ~CY_JUST_SET);
  1949. #endif
  1950. #if M88000
  1951.       /* d = -1 + cy
  1952.      m88000:    subu.ci    d,r0,r0 */
  1953.       PERFORM_ADC_CI(v, co, VALUE(0), VALUE(0), ci);
  1954.       RECURSE(ADC_CI, CNST(0), CNST(0), prune_hint & ~CY_JUST_SET);
  1955. #endif
  1956.     }
  1957.  
  1958.   /* Move instructions.
  1959.      Don't do this if we are just permitted to do one more instruction.  */
  1960.   if (allowed_cost > 1)
  1961.     {
  1962. #if SPARC || RS6000 || M88000 || AM29K
  1963.       /* d = 0x80000000
  1964.      sparc:        sethi    %hi(0x80000000),d
  1965.      rs6000:    liu    d,0x8000
  1966.      m88000:    or.u    d,r0,0x8000
  1967.      am29k:        cpeq    d,gr1,gr1 */
  1968.       PERFORM_COPY(v, co, VALUE_MIN_SIGNED, ci);
  1969.       RECURSE(COPY, CNST_0x80000000, 0, prune_hint & ~CY_JUST_SET);
  1970.       /* d = -1
  1971.      sparc:        mov    -1,d
  1972.      rs6000:    lil    d,-1
  1973.      m88000:    subu    d,r0,1
  1974.      am29k:        constn    d,1 */
  1975.       PERFORM_COPY(v, co, VALUE(-1), ci);
  1976.       RECURSE(COPY, CNST(-1), 0, prune_hint & ~CY_JUST_SET);
  1977.       /* d = 1
  1978.      sparc:        mov    1,d
  1979.      rs6000:    lil    d,1
  1980.      m88000:    addu    d,r0,1
  1981.      am29k:        const    d,1 */
  1982.       PERFORM_COPY(v, co, VALUE(1), ci);
  1983.       RECURSE(COPY, CNST(1), 0, prune_hint & ~CY_JUST_SET);
  1984. #endif
  1985. #if RS6000 || AM29K    /* sparc and 88k should not need this. */
  1986.       /* d = 0
  1987.      sparc:        mov    0,d
  1988.      rs6000:    lil    d,0
  1989.      m88000:    or    d,r0,0
  1990.      am29k:        const    d,0 */
  1991.       PERFORM_COPY(v, co, VALUE(0), ci);
  1992.       RECURSE(COPY, CNST(0), 0, prune_hint & ~CY_JUST_SET);
  1993. #endif
  1994. #if M88000
  1995.       /* d = 0x7fffffff
  1996.      m88000:    set    d,r0,31<0> */
  1997.       PERFORM_COPY(v, co, VALUE_MAX_SIGNED, ci);
  1998.       RECURSE(COPY, CNST_0x7FFFFFFF, 0, prune_hint & ~CY_JUST_SET);
  1999. #endif
  2000.     }
  2001.  
  2002. #ifdef TIMING
  2003.   timings[allowed_cost] += cputime() - time_start;
  2004. #endif
  2005. }
  2006. #endif
  2007.  
  2008. /* This function is commented above, before the previous function.  */
  2009.  
  2010. #if M68000 || I386 || PYR
  2011. void
  2012. synth(insn_t *sequence,
  2013.       int n_insns,
  2014.       word *values,
  2015.       int n_values,
  2016.       word goal_value,
  2017.       int allowed_cost,
  2018.       int ci,
  2019.       int prune_hint)
  2020. {
  2021.   int s1, s2;
  2022.   word v, r1, r2;
  2023.   int co;
  2024.   int last_dest;
  2025.  
  2026.   if (n_insns > 0)
  2027.     last_dest = sequence[n_insns - 1].d;
  2028.   else
  2029.     last_dest = -1;
  2030.  
  2031.   /* Binary operations with carry-in.  */
  2032.   if (ci >= 0 && (prune_hint & CY_0) == 0 && flag_use_carry)
  2033.     {
  2034.       for (s1 = n_values - 1; s1 >= 0; s1--)
  2035.     {
  2036.       r1 = values[s1];
  2037.       for (s2 = n_values - 1; s2 >= 0; s2--)
  2038.         {
  2039.           r2 = values[s2];
  2040.  
  2041.           if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
  2042.         {
  2043.           /* We are in a leaf node.  CY was not set (to 1 or to a
  2044.              data dependent value) by the previous insn.
  2045.  
  2046.              So one of the input operands has to be the result
  2047.              operand of the previous insn for that insn to be
  2048.              meaningful.  */
  2049.           if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
  2050.             continue;
  2051.         }
  2052.  
  2053. #if M68000 || I386 || PYR
  2054.           /* m68000:    addx
  2055.          i80386:    adc
  2056.          pyramid:    addwc */
  2057.           PERFORM_ADD_CIO(v, co, r1, r2, ci);
  2058.           CRECURSE_2OP(ADD_CIO, s1, s1, s2, 1, CY_JUST_SET);
  2059. #endif
  2060. #if M68000 || I386
  2061.           if (s1 != s2)
  2062.         {
  2063.           /* m68000:    subx
  2064.              i80386:    sbb */
  2065.           PERFORM_SUB_CIO(v, co, r1, r2, ci);
  2066.           CRECURSE_2OP(SUB_CIO, s1, s1, s2, 1, CY_JUST_SET);
  2067.         }
  2068. #endif
  2069. #if PYR
  2070.           if (s1 != s2)
  2071.         {
  2072.           /* pyramid:    subwb */
  2073.           PERFORM_ADC_CIO(v, co, r1, r2, ci);
  2074.           CRECURSE_2OP(ADC_CIO, s1, s1, s2, 1, CY_JUST_SET);
  2075.         }
  2076. #endif
  2077.         }
  2078.     }
  2079.     }
  2080.  
  2081.   /* Binary operations without carry-in.  */
  2082.   for (s1 = n_values - 1; s1 >= 0; s1--)
  2083.     {
  2084.       r1 = values[s1];
  2085.       for (s2 = n_values - 1; s2 >= 0; s2--)
  2086.     {
  2087.       r2 = values[s2];
  2088.  
  2089.       if (allowed_cost <= 1)
  2090.         {
  2091.           /* We are in a leaf node.
  2092.  
  2093.          So one of the input operands has to be the result operand
  2094.          of the previous insn for that insn to be meaningful.  */
  2095.           if (last_dest >= 0 && s1 != last_dest && s2 != last_dest)
  2096.         continue;
  2097.         }
  2098.  
  2099. #if M68000 || I386 || PYR
  2100.       /* m68000:    add
  2101.          i80386:    add
  2102.          pyramid:    addw */
  2103.       PERFORM_ADD_CO(v, co, r1, r2, ci);
  2104.       CRECURSE_2OP(ADD_CO, s1, s1, s2, 1, CY_JUST_SET);
  2105. #endif
  2106.       if (s1 != s2)
  2107.         {
  2108. #if M68000 || I386
  2109.           /* m68000:    sub
  2110.          i80386:    sub */
  2111.           PERFORM_SUB_CO(v, co, r1, r2, ci);
  2112.           CRECURSE_2OP(SUB_CO, s1, s1, s2, 1, CY_JUST_SET);
  2113. #endif
  2114. #if PYR
  2115.           /* pyramid:    subw */
  2116.           PERFORM_ADC_CO(v, co, r1, r2, ci);
  2117.           CRECURSE_2OP(ADC_CO, s1, s1, s2, 1, CY_JUST_SET);
  2118. #endif
  2119. #if M68000
  2120.           PERFORM_AND(v, co, r1, r2, ci);
  2121.           CRECURSE_2OP(AND, s1, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  2122.  
  2123.           PERFORM_IOR(v, co, r1, r2, ci);
  2124.           CRECURSE_2OP(IOR, s1, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  2125.  
  2126.           PERFORM_XOR(v, co, r1, r2, ci);
  2127.           CRECURSE_2OP(XOR, s1, s1, s2, 1, prune_hint & ~CY_JUST_SET);
  2128. #endif
  2129. #if I386
  2130.           PERFORM_AND_RC(v, co, r1, r2, ci);
  2131.           CRECURSE_2OP(AND_RC, s1, s1, s2, 1, CY_JUST_SET | CY_0);
  2132.  
  2133.           PERFORM_IOR_RC(v, co, r1, r2, ci);
  2134.           CRECURSE_2OP(IOR_RC, s1, s1, s2, 1, CY_JUST_SET | CY_0);
  2135.  
  2136.           PERFORM_XOR_RC(v, co, r1, r2, ci);
  2137.           CRECURSE_2OP(XOR_RC, s1, s1, s2, 1, CY_JUST_SET | CY_0);
  2138. #endif
  2139. #if PYR
  2140.           PERFORM_AND_CC(v, co, r1, r2, ci);
  2141.           CRECURSE_2OP(AND_CC, s1, s1, s2, 1, 0);
  2142.  
  2143.           PERFORM_ANDC_CC(v, co, r1, r2, ci);
  2144.           CRECURSE_2OP(ANDC_CC, s1, s1, s2, 1, 0);
  2145.  
  2146.           PERFORM_IOR_CC(v, co, r1, r2, ci);
  2147.           CRECURSE_2OP(IOR_CC, s1, s1, s2, 1, 0);
  2148.  
  2149.           PERFORM_XOR_CC(v, co, r1, r2, ci);
  2150.           CRECURSE_2OP(XOR_CC, s1, s1, s2, 1, 0);
  2151. #endif
  2152. #if I386
  2153.           PERFORM_CMP(v, co, r1, r2, ci);
  2154.           /* kludge: lie that the result is written to
  2155.          register <n_values>. */
  2156.           CRECURSE_2OP(CMP, n_values, s1, s2, 1, CY_JUST_SET);
  2157. #endif
  2158.         }
  2159. #if M68000 || I386 || PYR
  2160.       /* Exchange registers.  An ugly kludge.  */
  2161.       if (s1 < s2)
  2162.         {
  2163.           values[s2] = r1;
  2164.           /* Assign r2 to v to make `recurse' and rely on `recurse'
  2165.          to handle the writing of it to the values array.  */
  2166.           v = r2;
  2167.           CRECURSE_2OP(EXCHANGE, s1, s1, s2, 1,
  2168.                prune_hint & ~CY_JUST_SET);
  2169.           values[s2] = r2;
  2170.         }
  2171. #endif
  2172.     }
  2173.     }
  2174.  
  2175.   /* Unary operations with carry-in.  */
  2176.   if (ci >= 0 && (prune_hint & CY_0) == 0 && flag_use_carry)
  2177.     {
  2178.       for (s1 = n_values - 1; s1 >= 0; s1--)
  2179.     {
  2180.       r1 = values[s1];
  2181.  
  2182.       if (allowed_cost <= 1 && (prune_hint & CY_JUST_SET) == 0)
  2183.         {
  2184.           /* We are in a leaf node.  CY was not set (to 1 or to a
  2185.          data dependent value) by the previous insn.
  2186.  
  2187.          The input operand has to be the result operand of the
  2188.          previous insn for that insn to be meaningful.  */
  2189.           if (last_dest >= 0 && s1 != last_dest)
  2190.         continue;
  2191.         }
  2192.  
  2193. #if I386 || PYR
  2194.       /* d,cy = r1 + 1 + cy
  2195.          i80386:    adc    1,d
  2196.          pyramid:    addwc    $1,d */
  2197.       PERFORM_ADD_CIO(v, co, r1, VALUE(1), ci);
  2198.       CRECURSE_2OP(ADD_CIO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2199. #endif
  2200. #if I386
  2201.       /* d,cy = r1 - 1 - cy
  2202.          i80386:    sbb    1,d */
  2203.       PERFORM_SUB_CIO(v, co, r1, VALUE(1), ci);
  2204.       CRECURSE_2OP(SUB_CIO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2205. #endif
  2206. #if PYR
  2207.       /* d,cy = r1 + (-2) + cy
  2208.          pyramid:    subwb    $1,d */
  2209.       PERFORM_ADC_CIO(v, co, r1, VALUE(1), ci);
  2210.       CRECURSE_2OP(ADC_CIO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2211. #endif
  2212. #if I386 || PYR
  2213.       /* d,cy = r1 + (-1) + cy
  2214.          i80386:    adc    -1,d
  2215.          pyramid:    addwc    $-1,d */
  2216.       PERFORM_ADD_CIO(v, co, r1, VALUE(-1), ci);
  2217.       CRECURSE_2OP(ADD_CIO, s1, s1, CNST(-1), 1, CY_JUST_SET);
  2218. #endif
  2219. #if I386
  2220.       /* d,cy = r1 - -1 - cy
  2221.          i80386:    sbb    -1,d */
  2222.       PERFORM_SUB_CIO(v, co, r1, VALUE(-1), ci);
  2223.       CRECURSE_2OP(SUB_CIO, s1, s1, CNST(-1), 1, CY_JUST_SET);
  2224. #endif
  2225. #if PYR
  2226.       /* d,cy = r1 + cy          [or if you prefer, r1 + 0 + cy]
  2227.          pyramid:    subwb    $-1,d */
  2228.       PERFORM_ADC_CIO(v, co, r1, VALUE(-1), ci);
  2229.       CRECURSE_2OP(ADC_CIO, s1, s1, CNST(-1), 1, CY_JUST_SET);
  2230. #endif
  2231. #if I386 || PYR
  2232.       /* d,cy = r1 + cy
  2233.          i80386:    adc    0,d
  2234.          pyramid:    addwc    $0,d */
  2235.       PERFORM_ADD_CIO(v, co, r1, VALUE(0), ci);
  2236.       CRECURSE_2OP(ADD_CIO, s1, s1, CNST(0), 1, CY_JUST_SET);
  2237. #endif
  2238. #if I386
  2239.       /* d,cy = r1 - cy
  2240.          i80386:    sbb    0,d */
  2241.       PERFORM_SUB_CIO(v, co, r1, VALUE(0), ci);
  2242.       CRECURSE_2OP(SUB_CIO, s1, s1, CNST(0), 1, CY_JUST_SET);
  2243. #endif
  2244. #if PYR
  2245.       /* d,cy = r1 + (-1) + cy
  2246.          pyramid:    subwb    $0,d */
  2247.       PERFORM_ADC_CIO(v, co, r1, VALUE(0), ci);
  2248.       CRECURSE_2OP(ADC_CIO, s1, s1, CNST(0), 1, CY_JUST_SET);
  2249. #endif
  2250. #if M68000
  2251.       /* d,cy = 0 - r1 - cy
  2252.          m68000:     negx    d */
  2253.       PERFORM_SUB_CIO(v, co, VALUE(0), r1, ci);
  2254.       CRECURSE_2OP(SUB_CIO, s1, CNST(0), s1, 1, CY_JUST_SET);
  2255. #endif
  2256. #if M68000
  2257.       /* d,cy = circular rotate left thru carry
  2258.          m68000:    roxll    #1,d */
  2259.       PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(1), ci);
  2260.       CRECURSE_2OP(ROTATEXL_CIO, s1, s1, CNST(1), SHIFT_COST(1), CY_JUST_SET);
  2261. #endif
  2262. #if I386
  2263.       PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2264.       CRECURSE_2OP(ROTATEXL_CIO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);
  2265.  
  2266.       PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(1), ci);
  2267.       CRECURSE_2OP(ROTATEXL_CIO, s1, s1, CNST(1), 2, CY_JUST_SET);
  2268. #endif
  2269.     }
  2270.     }
  2271.  
  2272.   /* Unary operations without carry-in.  */
  2273.   for (s1 = n_values - 1; s1 >= 0; s1--)
  2274.     {
  2275.       r1 = values[s1];
  2276.  
  2277.       if (allowed_cost <= 1)
  2278.     {
  2279.       /* We are in a leaf node.
  2280.  
  2281.          The input operand has to be the result operand of the
  2282.          previous insns for that insn to be meaningful.  */
  2283.       if (last_dest >= 0 && s1 != last_dest)
  2284.         continue;
  2285.     }
  2286.       else
  2287.     {
  2288.       /* Certain instructions should not terminate a sequence.  So we
  2289.          only generate them in non-leaf nodes.  */
  2290. #if M68000 || I386 || PYR
  2291.       /* d = r1
  2292.          m68000:    move    s1,d
  2293.          i80386:    move    s1,d
  2294.          pyramid:    movw    s1,d */
  2295.       PERFORM_COPY(v, co, r1, ci);
  2296.       CRECURSE_NEW(COPY, n_values, s1, CNST(0), 1,
  2297.                prune_hint & ~CY_JUST_SET);
  2298. #endif
  2299. #if I386
  2300.       /* cmp kludge: lie that the result is written to register
  2301.          <n_values>. */
  2302.  
  2303.       /* i80386:    cmp    -1,s1 */
  2304.       PERFORM_CMP(v, co, r1, VALUE(-1), ci);
  2305.       CRECURSE_2OP(CMP, n_values, s1, CNST(-1), 1, CY_JUST_SET);
  2306.  
  2307.       /* i80386:    cmp    1,s1 */
  2308.       PERFORM_CMP(v, co, r1, VALUE(1), ci);
  2309.       CRECURSE_2OP(CMP, n_values, s1, CNST(1), 1, CY_JUST_SET);
  2310.  
  2311.       /* i80386:    cmp    0x7fffffff,s1 */
  2312.       PERFORM_CMP(v, co, r1, VALUE_MAX_SIGNED, ci);
  2313.       CRECURSE_2OP(CMP, n_values, s1, CNST_0x7FFFFFFF, 2, CY_JUST_SET);
  2314.  
  2315.       /* i80386:    cmp    0x80000000,s1 */
  2316.       PERFORM_CMP(v, co, r1, VALUE_MIN_SIGNED, ci);
  2317.       CRECURSE_2OP(CMP, n_values, s1, CNST_0x80000000, 2, CY_JUST_SET);
  2318. #endif
  2319.     }
  2320.  
  2321. #if M68000 || PYR
  2322.       PERFORM_LSHIFTR_CO(v, co, r1, VALUE(1), ci);
  2323.       CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(1), SHIFT_COST(1), CY_JUST_SET);
  2324.  
  2325.       PERFORM_ASHIFTR_CO(v, co, r1, VALUE(1), ci);
  2326.       CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(1), SHIFT_COST(1), CY_JUST_SET);
  2327.  
  2328.       PERFORM_SHIFTL_CO(v, co, r1, VALUE(1), ci);
  2329.       CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(1), SHIFT_COST(1), CY_JUST_SET);
  2330.  
  2331.       /* Pyramids's rotlw and rotrw clobber cy */
  2332. #endif
  2333. #if M68000
  2334.       PERFORM_ROTATEL_CO(v, co, r1, VALUE(1), ci);
  2335.       CRECURSE_2OP(ROTATEL_CO, s1, s1, CNST(1), SHIFT_COST(1), CY_JUST_SET);
  2336. #endif
  2337. #if PYR
  2338.       PERFORM_LSHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2339.       CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 1, CY_JUST_SET);
  2340.  
  2341.       PERFORM_ASHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2342.       CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 1, CY_JUST_SET);
  2343.  
  2344.       PERFORM_SHIFTL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2345.       CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(BITS_PER_WORD-1), 1, CY_JUST_SET);
  2346.  
  2347.       /* Pyramids's rotlw and rotrw clobber cy */
  2348. #endif
  2349. #if I386
  2350.       PERFORM_LSHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2351.       CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);
  2352.  
  2353.       PERFORM_ASHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2354.       CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);
  2355.  
  2356.       PERFORM_SHIFTL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2357.       CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);
  2358.  
  2359.       PERFORM_ROTATEL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2360.       CRECURSE_2OP(ROTATEL_CO, s1, s1, CNST(BITS_PER_WORD-1), 2, CY_JUST_SET);
  2361.  
  2362.       PERFORM_LSHIFTR_CO(v, co, r1, VALUE(1), ci);
  2363.       CRECURSE_2OP(LSHIFTR_CO, s1, s1, CNST(1), 2, CY_JUST_SET);
  2364.  
  2365.       PERFORM_ASHIFTR_CO(v, co, r1, VALUE(1), ci);
  2366.       CRECURSE_2OP(ASHIFTR_CO, s1, s1, CNST(1), 2, CY_JUST_SET);
  2367.  
  2368.       PERFORM_SHIFTL_CO(v, co, r1, VALUE(1), ci);
  2369.       CRECURSE_2OP(SHIFTL_CO, s1, s1, CNST(1), 2, CY_JUST_SET);
  2370.  
  2371.       PERFORM_ROTATEL_CO(v, co, r1, VALUE(1), ci);
  2372.       CRECURSE_2OP(ROTATEL_CO, s1, s1, CNST(1), 2, CY_JUST_SET);
  2373. #endif
  2374. #if M68000
  2375.       /* m68000:    andw    $1,d */
  2376.       PERFORM_AND(v, co, r1, VALUE(1), ci);
  2377.       CRECURSE_2OP(AND, s1, s1, CNST(1), 1, prune_hint & ~CY_JUST_SET);
  2378.  
  2379.       PERFORM_AND(v, co, r1, VALUE_MIN_SIGNED, ci);
  2380.       CRECURSE_2OP(AND, s1, s1, CNST_0x80000000, 2, prune_hint & ~CY_JUST_SET);
  2381.  
  2382.       PERFORM_IOR(v, co, r1, VALUE_MIN_SIGNED, ci);
  2383.       CRECURSE_2OP(IOR, s1, s1, CNST_0x80000000, 2, prune_hint & ~CY_JUST_SET);
  2384.  
  2385.       /* d = r1 ^ 1
  2386.      m68000:    eorw    #1,d */
  2387.       PERFORM_XOR(v, co, r1, VALUE(1), ci);
  2388.       CRECURSE_2OP(XOR, s1, s1, CNST(1), 1, prune_hint & ~CY_JUST_SET);
  2389.  
  2390.       PERFORM_XOR(v, co, r1, VALUE_MIN_SIGNED, ci);
  2391.       CRECURSE_2OP(XOR, s1, s1, CNST_0x80000000, 2, prune_hint & ~CY_JUST_SET);
  2392. #endif
  2393. #if I386
  2394.       /* i80386:    andb    $1,d */
  2395.       PERFORM_AND_RC(v, co, r1, VALUE(1), ci);
  2396.       CRECURSE_2OP(AND_RC, s1, s1, CNST(1), 1, CY_JUST_SET | CY_0);
  2397.  
  2398.       PERFORM_AND_RC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2399.       CRECURSE_2OP(AND_RC, s1, s1, CNST_0x80000000, 2, CY_JUST_SET | CY_0);
  2400.  
  2401.       PERFORM_IOR_RC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2402.       CRECURSE_2OP(IOR_RC, s1, s1, CNST_0x80000000, 2, CY_JUST_SET | CY_0);
  2403.  
  2404.       /* d = r1 ^ 1
  2405.      i80386:    xorb    $1,d */
  2406.       PERFORM_XOR_RC(v, co, r1, VALUE(1), ci);
  2407.       CRECURSE_2OP(XOR_RC, s1, s1, CNST(1), 1, CY_JUST_SET | CY_0);
  2408.  
  2409.       PERFORM_XOR_RC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2410.       CRECURSE_2OP(XOR_RC, s1, s1, CNST_0x80000000, 2, CY_JUST_SET | CY_0);
  2411. #endif
  2412. #if PYR
  2413.       PERFORM_AND_CC(v, co, r1, VALUE(1), ci);
  2414.       CRECURSE_2OP(AND_CC, s1, s1, CNST(1), 1, 0);
  2415.  
  2416.       PERFORM_AND_CC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2417.       CRECURSE_2OP(AND_CC, s1, s1, CNST_0x80000000, 2, 0);
  2418.  
  2419.       PERFORM_IOR_CC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2420.       CRECURSE_2OP(IOR_CC, s1, s1, CNST_0x80000000, 2, 0);
  2421.  
  2422.       /* d = r1 ^ 1
  2423.      pyramid:    xorw    $1,d */
  2424.       PERFORM_XOR_CC(v, co, r1, VALUE(1), ci);
  2425.       CRECURSE_2OP(XOR_CC, s1, s1, CNST(1), 1, 0);
  2426.  
  2427.       PERFORM_XOR_CC(v, co, r1, VALUE_MIN_SIGNED, ci);
  2428.       CRECURSE_2OP(XOR_CC, s1, s1, CNST_0x80000000, 2, 0);
  2429. #endif
  2430. #if M68000 || I386
  2431.       /* d = ~r1
  2432.      m68000:    not    d
  2433.      i80386:    not    d */
  2434.       PERFORM_SUB(v, co, VALUE(-1), r1, ci);
  2435.       CRECURSE_2OP(SUB, s1, CNST(-1), s1, 1, prune_hint & ~CY_JUST_SET);
  2436. #endif
  2437. #if PYR
  2438.       /* d = ~r1
  2439.      pyramid:    mcomw    s1,d */
  2440.       /* We need a new insn: SUB_CC, for Subtract and Clobber Carry  */
  2441. #endif
  2442. #if I386
  2443.       /* d = r1 + 1
  2444.      i80386:    inc    d */
  2445.       PERFORM_ADD(v, co, r1, VALUE(1), ci);
  2446.       CRECURSE_2OP(ADD, s1, s1, CNST(1), 2, prune_hint & ~CY_JUST_SET);
  2447. #endif
  2448. #if PYR
  2449.       /* d = r1 + 1
  2450.      pyramid:    mova    1(s1),d */
  2451.       PERFORM_ADD(v, co, r1, VALUE(1), ci);
  2452.       RECURSE(ADD, s1, CNST(1), prune_hint & ~CY_JUST_SET);
  2453. #endif
  2454. #if I386
  2455.       /* d = r1 - 1
  2456.      i80386:    dec    d */
  2457.       PERFORM_SUB(v, co, r1, VALUE(1), ci);
  2458.       CRECURSE_2OP(SUB, s1, s1, CNST(1), 1, prune_hint & ~CY_JUST_SET);
  2459. #endif
  2460. #if PYR
  2461.       /* d = r1 - 1
  2462.      pyramid:    mova    -1(s1),d */
  2463.       PERFORM_ADD(v, co, r1, VALUE(-1), ci);
  2464.       RECURSE(ADD, s1, CNST(-1), prune_hint & ~CY_JUST_SET);
  2465. #endif
  2466. #if M68000 || I386 || PYR
  2467.       /* d,cy = r1 + 1
  2468.      m68000:    addq    1,d
  2469.      i80386:    add    1,d [short immediate form]
  2470.      pyramid:    addw    $1,d */
  2471.       PERFORM_ADD_CO(v, co, r1, VALUE(1), ci);
  2472.       CRECURSE_2OP(ADD_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2473. #endif
  2474. #if M68000 || I386
  2475.       /* d,cy = r1 - 1
  2476.      m68000:    subq    1,d
  2477.      i80386:    sub    1,d [short immediate form] */
  2478.       PERFORM_SUB_CO(v, co, r1, VALUE(1), ci);
  2479.       CRECURSE_2OP(SUB_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2480. #endif
  2481. #if PYR && 0            /* same effect as addw $-1,d */
  2482.       /* d,cy = r1 + (-1)
  2483.      pyramid:    subw    1,d */
  2484.       PERFORM_ADC_CO(v, co, r1, VALUE(1), ci);
  2485.       CRECURSE_2OP(ADC_CO, s1, s1, CNST(1), 1, CY_JUST_SET);
  2486. #endif
  2487. #if M68000
  2488.       /* d,cy = r1 + (-1)
  2489.      m68000:    add    -1,d */
  2490.       PERFORM_ADD_CO(v, co, r1, VALUE(-1), ci);
  2491.       CRECURSE_2OP(ADD_CO, s1, s1, CNST(-1), 2, CY_JUST_SET);
  2492. #endif
  2493. #if I386 || PYR
  2494.       /* d,cy = r1 + (-1)
  2495.      i80386:    add    -1,d
  2496.      pyramid:    addw    $-1,d */
  2497.       PERFORM_ADD_CO(v, co, r1, VALUE(-1), ci);
  2498.       CRECURSE_2OP(ADD_CO, s1, s1, CNST(-1), 1, CY_JUST_SET);
  2499. #endif
  2500. #if M68000
  2501.       /* d,cy = r1 - (-1)
  2502.      m68000:    sub    -1,d */
  2503.       PERFORM_SUB_CO(v, co, r1, VALUE(-1), ci);
  2504.       CRECURSE_2OP(SUB_CO, s1, s1, CNST(-1), 2, CY_JUST_SET);
  2505. #endif
  2506. #if I386
  2507.       /* d,cy = r1 - (-1)
  2508.      i80386:    sub    -1,d */
  2509.       PERFORM_SUB_CO(v, co, r1, VALUE(-1), ci);
  2510.       CRECURSE_2OP(SUB_CO, s1, s1, CNST(-1), 1, CY_JUST_SET);
  2511. #endif
  2512. #if M68000 || I386
  2513.       /* d,cy = -r1
  2514.      m68000:    neg    d
  2515.      i80386:    neg    d */
  2516.       PERFORM_SUB_CO(v, co, VALUE(0), r1, ci);
  2517.       CRECURSE_2OP(SUB_CO, s1, CNST(0), s1, 1, CY_JUST_SET);
  2518. #endif
  2519. #if PYR
  2520.       /* d,cy = 0 + (-r1)
  2521.      pyramid:    rsubw    $0,d */
  2522.       PERFORM_ADC_CO(v, co, VALUE(0), r1, ci);
  2523.       CRECURSE_2OP(ADC_CO, s1, CNST(0), s1, 1, CY_JUST_SET);
  2524. #endif
  2525.     }
  2526.  
  2527. #if M68020 && !M68000        /* don't do this for plain 68000 */
  2528.   /* kludge for immediate shift on 68k */
  2529.   if (last_dest >= 0 && last_dest == n_values - 1
  2530.       && values[last_dest] == VALUE(BITS_PER_WORD-1)
  2531.       && sequence[n_insns - 1].opcode == COPY)
  2532.     {
  2533.       for (s1 = n_values - 2; s1 >= 0; s1--)
  2534.     {
  2535.       r1 = values[s1];
  2536.  
  2537.       PERFORM_LSHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2538.       CRECURSE_2OP(LSHIFTR_CO, s1, s1, last_dest, 1, CY_JUST_SET);
  2539.  
  2540.       PERFORM_ASHIFTR_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2541.       CRECURSE_2OP(ASHIFTR_CO, s1, s1, last_dest, 1, CY_JUST_SET);
  2542.  
  2543.       PERFORM_SHIFTL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2544.       CRECURSE_2OP(SHIFTL_CO, s1, s1, last_dest, 1, CY_JUST_SET);
  2545.  
  2546.       PERFORM_ROTATEL_CO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2547.       CRECURSE_2OP(ROTATEL_CO, s1, s1, last_dest, 1, CY_JUST_SET);
  2548.  
  2549.       if (ci >= 0)
  2550.         {
  2551.           PERFORM_ROTATEXL_CIO(v, co, r1, VALUE(BITS_PER_WORD-1), ci);
  2552.           CRECURSE_2OP(ROTATEXL_CIO, s1, s1, last_dest, 1, CY_JUST_SET);
  2553.         }
  2554.     }
  2555.     }
  2556. #endif
  2557.  
  2558.   if (ci >= 0 && (prune_hint & CY_0) == 0 && flag_use_carry
  2559.       && (allowed_cost <= 1 ? ((prune_hint & CY_JUST_SET) != 0) : 1))
  2560.     {
  2561. #if M68000 || I386
  2562.       /* d = -cy, cy = cy
  2563.      m68000:    subx    d,d
  2564.      i80386:    sbb    d,d */
  2565.       PERFORM_SUB_CIO(v, co, VALUE(0), VALUE(0), ci);
  2566.       CRECURSE_NEW(SUB_CIO, n_values, n_values, n_values, 1,
  2567.            prune_hint & ~CY_JUST_SET); /* cy not really affected */
  2568. #endif
  2569. #if PYR
  2570.       /* d = -cy, cy = cy
  2571.      pyramid:    subwb    d,d */
  2572.       PERFORM_ADC_CIO(v, co, VALUE(0), VALUE(0), ci);
  2573.       CRECURSE_NEW(ADC_CIO, n_values, n_values, n_values, 1,
  2574.            prune_hint & ~CY_JUST_SET); /* cy not really affected */
  2575. #endif
  2576. #if I386 /* slow on m68000 */
  2577.       /* i80386:    cmc */
  2578.       co = ci ^ 1;
  2579.       CRECURSE_2OP(COMCY, n_values, n_values, n_values, 1, CY_JUST_SET);
  2580. #endif
  2581.     }
  2582.  
  2583.   /* Move instructions.
  2584.      Don't do this if we are just permitted to do one more instruction.  */
  2585.   if (allowed_cost > 1)
  2586.     {
  2587. #if M68000 || PYR
  2588.       /* d = 0
  2589.      m68000:    moveq    0,d
  2590.      pyramid:    movw    0,d */
  2591.       PERFORM_COPY(v, co, VALUE(0), ci);
  2592.       CRECURSE_NEW(COPY, n_values, CNST(0), CNST(0), 1,
  2593.            prune_hint & ~CY_JUST_SET);
  2594. #endif
  2595. #if M68000 || I386
  2596.       /* d = 0, cy = 0
  2597.      m68000:    sub    d,d
  2598.      i80386:    sub    d,d */
  2599.       PERFORM_SUB_CO(v, co, r1, r1, ci);
  2600.       CRECURSE_NEW(SUB_CO, n_values, n_values, n_values, 1, CY_JUST_SET | CY_0);
  2601. #endif
  2602. #if PYR
  2603.       /* d = 0, cy = 0
  2604.      pyramid:    subw    d,d */
  2605.       PERFORM_ADC_CO(v, co, r1, r1, ci);
  2606.       CRECURSE_NEW(ADC_CO, n_values, n_values, n_values, 1, CY_JUST_SET | CY_0);
  2607. #endif
  2608. #if M68000
  2609.       /* d = 31
  2610.      m68000:    moveq    31,d */
  2611.       PERFORM_COPY(v, co, VALUE(BITS_PER_WORD-1), ci);
  2612.       CRECURSE_NEW(COPY, n_values, CNST(BITS_PER_WORD-1), CNST(0), 1,
  2613.            prune_hint & ~CY_JUST_SET);
  2614. #endif
  2615. #if M68000 || PYR
  2616.       /* d = 1
  2617.      m68000:    moveq    1,d
  2618.      pyramid:    movw    $1,d */
  2619.       PERFORM_COPY(v, co, VALUE(1), ci);
  2620.       CRECURSE_NEW(COPY, n_values, CNST(1), CNST(0), 1,
  2621.            prune_hint & ~CY_JUST_SET);
  2622.       /* d = -1
  2623.      m68000:    moveq    -1,d
  2624.      pyramid:    movw    $-1,d  */
  2625.       PERFORM_COPY(v, co, VALUE(-1), ci);
  2626.       CRECURSE_NEW(COPY, n_values, CNST(-1), CNST(0), 1,
  2627.            prune_hint & ~CY_JUST_SET);
  2628. #endif
  2629. #if M68000 || I386 || PYR    /* these cost 2 cost units */
  2630.       /* d = 0x80000000 */
  2631.       PERFORM_COPY(v, co, VALUE_MIN_SIGNED, ci);
  2632.       CRECURSE_NEW(COPY, n_values, CNST_0x80000000, CNST(0), 2,
  2633.            prune_hint & ~CY_JUST_SET);
  2634.  
  2635.       /* d = 0x7fffffff */
  2636.       PERFORM_COPY(v, co, VALUE_MAX_SIGNED, ci);
  2637.       CRECURSE_NEW(COPY, n_values, CNST_0x7FFFFFFF, CNST(0), 2,
  2638.            prune_hint & ~CY_JUST_SET);
  2639. #endif
  2640.     }
  2641. }
  2642. #endif
  2643.  
  2644. /* Call `synth' allowing deeper and deeper searches for each call.
  2645.    This way we achieve iterative deepening search.
  2646.  
  2647.    MAXMAX_COST is the maximum cost for any sequence we will accept.  */
  2648. void
  2649. main_synth(int maxmax_cost, int allowed_extra_cost)
  2650. {
  2651.   int max_cost;
  2652.   word values[0x100];
  2653.   insn_t sequence[0x100];
  2654.   int i, ii;
  2655.  
  2656.   init_immediates(tvalues);
  2657.   init_immediates(values);
  2658.   init_test_sets();
  2659.  
  2660.   /* Speed hack: Try to find random values that makes the goal function
  2661.      take a value != 0.  Many false sequences give 0 for all input,
  2662.      and this hack achieve quick reject of these sequences.  */
  2663.   for (i = 0; i < 50; i++)
  2664.     {
  2665.       for (ii = 0; ii < goal_function_arity; ii++)
  2666.     values[ii] = random_word();
  2667.       if ((*eval_goal_function)(values) != 0)
  2668.     break;
  2669.     }
  2670.  
  2671.   ii = 0;
  2672. #if KNOW_START
  2673.   switch (goal_function)
  2674.     {
  2675.     case FFS:
  2676. #if M88000
  2677.       /* Best ffs starting place.  */
  2678.       sequence[ii++] = (insn_t) { ADC_CO, CNST(0), 0, 1 };
  2679.       sequence[ii++] = (insn_t) { AND, 0, 1, 2 };
  2680. #endif
  2681.       break;
  2682.  
  2683.     case ZDEPI_FOR_MOVSI:
  2684. #if SPARC
  2685.       sequence[ii++] = (insn_t) { SUB, CNST(0), 0, 1 };
  2686.       sequence[ii++] = (insn_t) { AND, 0, 1, 2 };
  2687. #endif
  2688.       break;
  2689.     default: break;
  2690.     }
  2691. #endif
  2692.  
  2693.   fprintf(stderr, "Superoptimizing at cost");
  2694.   success = 0;
  2695.   for (max_cost = 1; max_cost <= maxmax_cost; max_cost++)
  2696.     {
  2697. #if TIMING
  2698.       for (i = 0; i <= max_cost; i++)
  2699.     timings[i] = 0;
  2700. #endif
  2701.  
  2702.       if (success)
  2703.     fprintf (stderr, "[cost %d]\n", max_cost + ii);
  2704.       else
  2705.     fprintf(stderr, " %d", max_cost + ii);
  2706.       fflush(stderr);
  2707.  
  2708.       i = run_program (sequence, ii, values);
  2709.  
  2710.       /* Don't pass CY_JUST_SET ever, since we don't know which of the
  2711.      predefined insn above set cy.  */
  2712.       synth(sequence, ii, values, goal_function_arity+ii,
  2713.         (*eval_goal_function)(values),
  2714.         max_cost, i, NO_PRUNE);
  2715.  
  2716. #ifdef STATISTICS
  2717.       if (isatty(fileno(stdout)) == isatty(fileno(stderr)))
  2718.     printf("\n");
  2719.       printf("heuristic accept count:%u\n", heuristic_accept_count);
  2720.       printf("heuristic reject count:%u\n", heuristic_reject_count);
  2721. #endif
  2722. #if TIMING
  2723.       for (i = 1; i <= max_cost; i++)
  2724.     printf ("time %d: %d\n", i, timings[i] - timings[i - 1]);
  2725. #endif
  2726.  
  2727.       if (success)
  2728.     {
  2729.       allowed_extra_cost--;
  2730.       if (allowed_extra_cost < 0)
  2731.         {
  2732.           static char *s[] = {"", "s"};
  2733.           fprintf(stderr, " [%d sequence%s found]\n", success,
  2734.               s[success != 1]);
  2735.           return;
  2736.         }
  2737.     }
  2738.     }
  2739.   fprintf(stderr, " failure.\n");
  2740. }
  2741.  
  2742. /* Create a function for each DEF_GOAL.  When optimized, these are very
  2743.    efficient.  */
  2744. #undef    DEF_GOAL
  2745. #ifdef __STDC__
  2746. #define DEF_GOAL(SYM,ARITY,NAME,CODE)         \
  2747. word SYM ## _func (const word *v)        \
  2748. GOAL_FUNCTION (ARITY, CODE)
  2749. #else
  2750. #define DEF_GOAL(SYM,ARITY,NAME,CODE)         \
  2751. word SYM/**/_func (v) word *v;            \
  2752. GOAL_FUNCTION (ARITY, CODE)
  2753. #endif
  2754. #define GOAL_FUNCTION(ARITY,CODE)        \
  2755. {                        \
  2756.   word r, v0, v1, v2, v3;            \
  2757.   switch (ARITY)                \
  2758.     {                        \
  2759.     default:                    \
  2760.       abort ();                    \
  2761.     case 4: v3 = v[3];                \
  2762.     case 3: v2 = v[2];                \
  2763.     case 2: v1 = v[1];                \
  2764.     case 1: v0 = v[0];                \
  2765.     }                        \
  2766.   CODE;                        \
  2767.   return r;                    \
  2768. }
  2769. #undef    DEF_SYNONYM
  2770. #define DEF_SYNONYM(SYM,NAME)
  2771. #include "goal.def"
  2772.  
  2773. struct
  2774. {
  2775.   char *fname;
  2776.   enum goal_func fcode;
  2777.   int arity;
  2778.   char *c_code;
  2779.   word (*function)(const word*);
  2780. } goal_table[] =
  2781. {
  2782. /* Start off with entries so that goal_names[i].fcode == i.  */
  2783. #undef    DEF_GOAL
  2784. #ifdef __STDC__
  2785. #define DEF_GOAL(SYM,ARITY,NAME,CODE) {NAME, SYM, ARITY, #CODE, SYM ## _func},
  2786. #else
  2787. #define DEF_GOAL(SYM,ARITY,NAME,CODE) {NAME, SYM, ARITY, "CODE", SYM/**/_func},
  2788. #endif
  2789. #undef    DEF_SYNONYM
  2790. #define DEF_SYNONYM(SYM,NAME)
  2791. #include "goal.def"
  2792.  
  2793. /* Now add the synonyms.  */
  2794. #undef    DEF_GOAL
  2795. #define DEF_GOAL(SYM,ARITY,NAME,CODE)
  2796. #undef    DEF_SYNONYM
  2797. #define DEF_SYNONYM(SYM,NAME) {NAME, SYM, 0, 0},
  2798. #include "goal.def"
  2799. };
  2800.  
  2801. #define GET_GOAL_NAME(X) (goal_table[X].fname)
  2802. #define GET_GOAL_ARITY(X) (goal_table[X].arity)
  2803. #define GET_GOAL_C_CODE(X) (goal_table[X].c_code)
  2804. #define GET_GOAL_FUNCTION(X) (goal_table[X].function)
  2805.  
  2806. int
  2807. main(int argc, char **argv)
  2808. {
  2809.   int maxmax_cost = 5;
  2810.   int allowed_extra_cost = 0;
  2811.   int flag_all = 0;
  2812.  
  2813.   goal_function = LAST_AND_UNUSED_GOAL_CODE;
  2814.  
  2815.   argv++;
  2816.   argc--;
  2817.  
  2818.   while (argc > 0)
  2819.     {
  2820.       char *arg = argv[0];
  2821.       int arglen = strlen(arg);
  2822.  
  2823.       if (arglen < 2)
  2824.     arglen = 2;
  2825.  
  2826.       if (!strncmp(arg, "-version", arglen))
  2827.     {
  2828.       printf ("GSO version %s\n", version_string);
  2829.       if (argc == 1)
  2830.         exit (0);
  2831.     }
  2832.       else if (!strncmp(arg, "-assembler", arglen))
  2833.     flag_output_assembler = 1;
  2834.       else if (!strncmp(arg, "-no-carry-insns", arglen))
  2835.     flag_use_carry = 0;
  2836.       else if (!strncmp(arg, "-all", arglen))
  2837.     flag_all = 1;
  2838.       else if (!strncmp(arg, "-max-cost", arglen))
  2839.     {
  2840.       argv++;
  2841.       argc--;
  2842.       if (argc == 0)
  2843.         {
  2844.           fprintf(stderr, "superoptimizer: argument to `-max-cost' expected\n");
  2845.           exit(-1);
  2846.         }
  2847.       maxmax_cost = atoi(argv[0]);
  2848.     }
  2849.       else if (!strncmp(arg, "-extra-cost", arglen))
  2850.     {
  2851.       argv++;
  2852.       argc--;
  2853.       if (argc == 0)
  2854.         {
  2855.           fprintf(stderr, "superoptimizer: argument `-extra-cost' expected\n");
  2856.           exit(-1);
  2857.         }
  2858.       allowed_extra_cost = atoi(argv[0]);
  2859.     }
  2860.       else if (!strncmp(arg, "-f", 2))
  2861.     {
  2862.       int i;
  2863.       for (i = 0; i < sizeof(goal_table) / sizeof(goal_table[0]); i++)
  2864.         {
  2865.           if (!strcmp(arg + 2, goal_table[i].fname))
  2866.         {
  2867.           goal_function = goal_table[i].fcode;
  2868.           goal_function_arity = GET_GOAL_ARITY(goal_function);
  2869.           eval_goal_function = GET_GOAL_FUNCTION(goal_function);
  2870.           break;
  2871.         }
  2872.         }
  2873.       if (goal_function == LAST_AND_UNUSED_GOAL_CODE)
  2874.         {
  2875.           fprintf(stderr,
  2876.               "superoptimizer: unknown goal function\n");
  2877.           exit(-1);
  2878.         }
  2879.     }
  2880.       else
  2881.     {
  2882.       fprintf(stderr, "superoptimizer: syntax error at command line\n");
  2883.       exit(-1);
  2884.     }
  2885.  
  2886.       argv++;
  2887.       argc--;
  2888.     }
  2889.  
  2890.   if (flag_all)
  2891.     {
  2892.       for (goal_function = 0; goal_function < LAST_AND_UNUSED_GOAL_CODE;
  2893.        goal_function++)
  2894.     {
  2895.       fprintf(stderr, "Searching for goal %s\n",
  2896.           GET_GOAL_NAME (goal_function));
  2897.  
  2898.       goal_function_arity = GET_GOAL_ARITY(goal_function);
  2899.       eval_goal_function = GET_GOAL_FUNCTION(goal_function);
  2900.       main_synth(maxmax_cost, allowed_extra_cost);
  2901.       if (success)
  2902.         fprintf(stderr, "%s\n", GET_GOAL_C_CODE(goal_function));
  2903.     }
  2904.       return 0;
  2905.     }
  2906.       
  2907.   if (goal_function == LAST_AND_UNUSED_GOAL_CODE)
  2908.     {
  2909.       fprintf(stderr, "superoptimizer: missing goal function definition\n");
  2910.       exit(-1);
  2911.     }
  2912.  
  2913.   fprintf(stderr, "Searching for %s\n", GET_GOAL_C_CODE(goal_function));
  2914.   main_synth(maxmax_cost, allowed_extra_cost);
  2915.   return !success;
  2916. }
  2917.  
  2918. /* Aux stuff that should go into a separate file.  */
  2919.  
  2920. int
  2921. ffs_internal(x)
  2922.      word x;
  2923. {
  2924.   int co, ci;
  2925.   word d;
  2926.   PERFORM_FFS(d, co, x, ci);
  2927.   return d;
  2928. }
  2929.  
  2930. const char clz_tab[] =
  2931. {
  2932.   32,31,30,30,29,29,29,29,28,28,28,28,28,28,28,28,
  2933.   27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,27,
  2934.   26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,
  2935.   26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,26,
  2936.   25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  2937.   25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  2938.   25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  2939.   25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,
  2940.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2941.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2942.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2943.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2944.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2945.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2946.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2947.   24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,
  2948. };
  2949.  
  2950. const char ctz_tab[] =
  2951. {
  2952.   8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2953.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2954.   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2955.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2956.   6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2957.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2958.   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2959.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2960.   7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2961.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2962.   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2963.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2964.   6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2965.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2966.   5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2967.   4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
  2968. };
  2969.  
  2970. const char ff1_tab[] =
  2971. {
  2972.   32,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,
  2973.   4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
  2974.   5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  2975.   5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  2976.   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  2977.   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  2978.   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  2979.   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  2980.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2981.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2982.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2983.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2984.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2985.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2986.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2987.   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
  2988. };
  2989.